user2274642 - 1 year ago 68
Java Question

# all possible combination of n sets

I have n Sets. each Set has different number of elements. I would like to write an algorithm which give me all possible combinations from the sets.
for example:
Lets say we have:

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

a combination should look like

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

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

``````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 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 variant. It is based on increasing an array of counters where the counter wraps and carries 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)+"}";

}
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download