所有可能的n组合

我有n套。 每个集合都有不同数量的元素。 我想写一个算法，它给出了所有可能的组合。 例如：让我们说：

S1={1,2}, S2={A,B,C}, S3={$,%,£,!} 

组合看起来应该是这样的

 C1={1,A,$} C2={1,A,%} 

……等可能组合的数量将是2*3*4 = 24

请帮我用Java编写这个算法。

提前谢谢了

Answer 1

递归是你的朋友：

 public class PrintSetComb{ public static void main(String[] args){ String[] set1 = {"1","2"}; String[] set2 = {"A","B","C"}; String[] set3 = {"$", "%", "£", "!"}; String[][] sets = {set1, set2, set3}; printCombinations(sets, 0, ""); } private static void printCombinations(String[][] sets, int n, String prefix){ if(n >= sets.length){ System.out.println("{"+prefix.substring(0,prefix.length()-1)+"}"); return; } for(String s : sets[n]){ printCombinations(sets, n+1, prefix+s+","); } } } 

回答OP关于将其概括为对象集的问题：

 import java.util.Arrays; public class PrintSetComb{ public static void main(String[] args){ Integer[] set1 = {1,2}; Float[] set2 = {2.0F,1.3F,2.8F}; String[] set3 = {"$", "%", "£", "!"}; Object[][] sets = {set1, set2, set3}; printCombinations(sets, 0, new Object[0]); } private static void printCombinations(Object[][] sets, int n, Object[] prefix){ if(n >= sets.length){ String outp = "{"; for(Object o: prefix){ outp = outp+o.toString()+","; } System.out.println(outp.substring(0,outp.length()-1)+"}"); return; } for(Object o : sets[n]){ Object[] newPrefix = Arrays.copyOfRange(prefix,0,prefix.length+1); newPrefix[newPrefix.length-1] = o; printCombinations(sets, n+1, newPrefix); } } } 

最后是一个迭代变体。 它基于增加计数器数组，计数器在达到集合大小时进行包装和携带：

 import java.util.Arrays; public class PrintSetCombIterative{ public static void main(String[] args){ String[] set1 = {"1","2"}; String[] set2 = {"A","B","C"}; String[] set3 = {"$", "%", "£", "!"}; Object[][] sets = {set1, set2, set3}; printCombinations(sets); } private static void printCombinations(Object[][] sets){ int[] counters = new int[sets.length]; do{ System.out.println(getCombinationString(counters, sets)); }while(increment(counters, sets)); } private static boolean increment(int[] counters, Object[][] sets){ for(int i=counters.length-1;i>=0;i--){ if(counters[i] < sets[i].length-1){ counters[i]++; return true; } else { counters[i] = 0; } } return false; } private static String getCombinationString(int[] counters, Object[][] sets){ String combo = "{"; for(int i = 0; i 

Answer 2

在有人想要矩阵而不是打印的情况下，我稍微修改了代码：

 public class TestSetCombinations2 { public static void main(String[] args) { Double[] set1 = {2.0,3.0}; Double[] set2 = {4.0,2.0,1.0}; Double[] set3 = {3.0, 2.0, 1.0, 5.0}; Double[] set4 = {1.0,1.0}; Object[][] sets = {set1, set2, set3, set4}; Object[][] combinations = getCombinations(sets); for (int i = 0; i < combinations.length; i++) { for (int j = 0; j < combinations[0].length; j++) { System.out.print(combinations[i][j]+" "); } System.out.println(); } } private static Object[][] getCombinations(Object[][] sets) { int[] counters = new int[sets.length]; int count = 1; int count2 = 0; for (int i = 0; i < sets.length; i++) { count *= sets[i].length; } Object[][] combinations = new Object[count][sets.length]; do{ combinations[count2++] = getCombinationString(counters, sets); } while(increment(counters, sets)); return combinations; } private static Object[] getCombinationString(int[] counters, Object[][] sets) { Object[] o = new Object[counters.length]; for(int i = 0; i=0;i--) { if(counters[i] < sets[i].length-1) { counters[i]++; return true; } else { counters[i] = 0; } } return false; } } 

Answer 3

krilid提供了很好的解决方案，我修改了一下以返回所有组合的列表。

 @Test public void testMap() throws Exception { char[] one = new char[]{'a', 'b', 'c'}; char[] two = new char[]{'d', 'e', 'f'}; char[] three = new char[]{'g', 'h', 'i', 'j'}; char[][] sets = new char[][]{one, two, three}; List> collector = new ArrayList<>(); ArrayList combo = new ArrayList<>(); combinations(collector, sets, 0, combo); System.out.println(collector); } private void combinations(List> collector, char[][] sets, int n, ArrayList combo) { if (n == sets.length) { collector.add(new ArrayList<>(combo)); return; } for (char c : sets[n]) { combo.add(c); combinations(collector, sets, n + 1, combo); combo.remove(combo.size() - 1); } }