java - Java:从输入字符串数组生成 nCr 数组并返回它
问题描述
我想从输入数组中返回所有可能组合的完整数组。我想生成 n 选择 k 组合,其中 k = 1 到 n。到目前为止,我一直非常失败。
static void combinationUtil(String[] arr, String data[], int start, int end, int index, int r, float[][] info) {
// Current combination is ready to be printed, print it
strat newStrat = new strat(0, 0, 0, null);
if (index == r) {
//THIS IS WHERE THE COMBINATION I WANT APPEARS
return;
}
for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
data[index] = arr[i];
combinationUtil(arr, data, i + 1, end, index + 1, r, info);
}
return;
}
public static void getCombinations(String[] arr, int n, int r, float[][] info) {
String[] data = new String[r];
combinationUtil(arr, data, 0, n - 1, 0, r, info);
}
public static void main(String[] args) throws IOException, InterruptedException {
//Array I want to get all k 1:n combinations of
String[] array = { "TST1", "TST2", "TST3"}
//start a timer because that's always fun
long startTime = System.nanoTime();
//cycle through all 'pick k values'
for (int i = 1; i < 8; i++) {
getCombinations(array, n, i, info);
}
//Math's up. How Long did that take?
long endTime = System.nanoTime();
//IDEALLY PRINT THE COMBINATIONAL ARRAY HERE
System.out.println(Arrays.deepToString(_____));
//Don't forget to print the time ;)
System.out.println("Duration: "+(endTime - startTime)+" ns");
}
我已经尝试了所有我能想到的和谷歌。从将“数据”数组传递给函数,将其与之前的自身连接,将旧数组复制到最新索引是最新“数据”的新数组,ArrayLists,Stacks,.push(),.add() ,获取可能组合的总数并将它们插入全局数组索引中......没什么......我被烧毁了......当然理想情况下,结果看起来像:
[["TST1"], ["TST2"], ["TST3"], ["TST1", "TST2"], ["TST1", "TST3"], ["TST2", "TST3"], ["TST1", "TST2", "TST3"]
在这一点上,甚至可以添加一点
"It is done. Go. Be happy!"
上面的代码运行良好,但是组合只出现在combinationUtil()中,而不是我想在main()中使用累积结果的地方。那么,我做错了什么?
解决方案
您想计算大小为 n 的数组中 r 元素的可能组合。你可以试试这段代码。我将该函数称为 nCr(不确定这是否是我们试图解决的问题的正确数学符号)
public static void main(String[] args) {
String[] array2 = { "TST1", "TST2", "TST3"};
List<List<String>> l = new ArrayList<>();
for (var i: Arrays.asList(0, 1, 2, 3)) {
l.addAll(nCr(array2, i));
}
System.out.println(l);
}
private static List<List<String>> nCr(String[] array, int r) {
List<List<String>> result = new ArrayList<>();
if (r == 0) return result;
if (r == 1) return nC1(array);
for (int i = 0; i < array.length - r + 1; i++) {
List<List<String>> result2 = nCr(
Arrays.copyOfRange(array, i + 1, array.length),
r - 1);
for (var x: result2 ) {
x.add(array[i]);
result.add(x);
}
}
return result;
}
private static List<List<String>> nC1(String[] array) {
List<List<String>> l = new ArrayList<>();
for (var x: array) {
l.add(new ArrayList<>(Arrays.asList(x)));
}
return l;
}
输出:
[[TST1], [TST2], [TST3], [TST2, TST1], [TST3, TST1], [TST3, TST2], [TST3, TST2, TST1]]
推荐阅读
- r - 如何创建计划目标以交叉先前地图目标的结果和新变量?
- text - 如何在 ModalRoute 上设置状态()?
- c# - 通过 nuget 安装时引用 Bootstrap 的问题
- java - 我们可以在 eclipse plugin_customization.ini 文件中保留 2 个或更多 org.eclipse.ui/KEY_CONFIGURATION_ID
- python - 如何检查数组中每个项目的while循环中的参数?
- java - 创建将不同的唯一字符串值映射到具有指定范围的唯一整数值
- python - Django 和时区,一天的开始:我应该在我的函数中 make_aware() 一次还是两次?
- java - Log4j2 不登录到日志文件
- jquery - 使用 Web api 查询获取 Dynamics-CRM 中的实体属性值
- c++ - QT5.3.2 + VTK6.1 C++程序长时间运行后随机退出