从不确定的金额中查找所有可能的组合

Question

给定一个列表;List<List<SomeType>>内部列表可以是任何大小，而外部列表可以是传递给函数的变量的大小，我需要找到包含元素的所有可能组合。

因为我的解释可能很差，所以这里有一个输入和输出示例。

输入：

[
['a', 'b'],
['c', 'd', 'e', 'f'],
['g', 'h'],
['i']
]

输出：

[
['a', 'c', 'g', 'i'],
['a', 'c', 'h', 'i'],
['a', 'd', 'g', 'i'],
['a', 'd', 'h', 'i'],
['a', 'e', 'g', 'i'],
['a', 'e', 'h', 'i'],
['a', 'f', 'g', 'i'],
['a', 'f', 'h', 'i'],
['b', 'c', 'g', 'i'],
['b', 'c', 'h', 'i'],
['b', 'd', 'g', 'i'],
['b', 'd', 'h', 'i'],
['b', 'e', 'g', 'i'],
['b', 'e', 'h', 'i'],
['b', 'f', 'g', 'i'],
['b', 'f', 'h', 'i']
]

对于如何完成这项工作，我绝对感到困惑。我根本无法理解它，任何帮助将不胜感激。

Answer 1

这是我的实现。它似乎工作正常。我使用 String[][] 作为输入，但您可以根据需要更改它。

public class Main {
/**
* This method nests (input.length) for loops to build the desired output.
* @param input The input, change the data type as needed
* @param i An index used to keep track of the element we are checking within the nested for loops
* @param output The output, again, change the data type as needed
* @param newElementOutput A String[] used to temporarily hold the elements of each String[] in the output.
*/
private static void runThrough(String[][] input, int i, ArrayList<String[]> output, String[] newElementOutput){
if(i < input.length - 1){
for(String element:input[i]){
newElementOutput[i] = element;
runThrough(input, i+1, output, newElementOutput);
}
}else if(i == input.length - 1){
for(String element:input[i]){
newElementOutput[i] = element;
output.add(Arrays.copyOf(newElementOutput, input.length));  // a copy so when newOutput changes, the array added to output will stay the same since the reference is different
}
}
}
public static void getCombinations(String[][] input, boolean printTest){
String[] newOutput = new String[input.length];
ArrayList<String[]> output = new ArrayList<>();
runThrough(input, 0, output, newOutput);
// Print the results, to check that everything is as it should
if (printTest) printResults(output);
}
private static void printResults(ArrayList<String[]> output){
System.out.println("Combinations:n");
for(String[] test:output){
for(String combination:test){
System.out.print(combination);
}
System.out.print("n");
}
/*
Since in the given example there are four sets of 2, 4, 2 and 1 elements, respectively,
there should be 2 * 4 * 2 * 1 = 16 different combinations
*/
System.out.println("nTotal number of combinations: " + output.size());
}
public static void main(String[] args){
String[][] arr = {
{"a", "b"},
{"c", "d", "e", "f"},
{"g", "h"},
{"i"}};
getCombinations(arr, true);
}
}

Answer 2

检查这个我认为这可以解决你的问题

public class Test {
public static void main(String a[]) {
List<List<String>> lists = Arrays.asList(Arrays.asList("a", "b"), Arrays.asList("c", "d", "e", "f"), Arrays.asList("g", "h"), Arrays.asList("i"));
System.out.println("lists = " + lists);
List<List<String>> out = getOutPut(new ArrayList<>(), lists);
System.out.println("out = " + out);
}
private static List<List<String>> getOutPut(List<String> conList, List<List<String>> lists) {
List<List<String>> out = new ArrayList<>();
if (lists.size() == 1) {
lists.get(0).forEach(s -> {
List<String> newList = new ArrayList<>(conList);
newList.add(s);
out.add(newList);
});
} else {
lists.get(0).forEach(s -> {
List<String> newList = new ArrayList<>(conList);
newList.add(s);
out.addAll(getOutPut(newList, lists.subList(1, lists.size())));
});
}
return out;
}
}