All possible combination of n sets

Question

I have n sets. Each set has a different number of elements. I would like to write an algorithm that gives me all possible combinations of sets. for example: Let's say we have:

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

the combination should look like

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

.... and so on, the number of possible combinations will be 2*3*4 = 24

Please help me write this algorithm in Java.

Thanks a lot at Advance

Answer 1

Recursion is your friend:

 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+","); } } } 

In response to a question from OP about generalizing it to sets of objects:

 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); } } } 

And finally, an iterative option. It is based on increasing the array of counters, where the counter wraps and carries around when it reaches the size of the set:

 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<counters.length;i++){ combo = combo+sets[i][counters[i]]+","; } return combo.substring(0,combo.length()-1)+"}"; } } 

Answer 2

In case someone wants to get a matrix instead of printing, I changed the code a bit:

 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<counters.length;i++) { o[i] = sets[i][counters[i]]; } return o; } 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; } }