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, let's 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
Please Help me to write this algorithm in Java.
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 question from OP about generalizing it to sets of Objects:
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:
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) + "}";
}
}
In the case someone wants the matrix instead of printing, I slightly modified the code:
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;
}
}
Great solution by krilid, I modified it a bit to return a list of all combinations.
@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<List<Character>> collector = new ArrayList<>();
ArrayList<Character> combo = new ArrayList<>();
combinations(collector, sets, 0, combo);
System.out.println(collector);
}
private void combinations(List<List<Character>> collector,
char[][] sets, int n,
ArrayList<Character> 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);
}
}
You can create a generic method to get the Cartesian product of different types and numbers of collections and their elements.
public static void main(String[] args) {
Set<Integer> a = Set.of(1, 2);
List<String> b = List.of("A", "B", "C");
Set<Character> c = Set.of('$', '%', '£', '!');
Set<Set<Object>> cpSet = cartesianProduct(HashSet::new, a, b, c);
List<List<Object>> cpList = cartesianProduct(ArrayList::new, a, b, c);
// output, order may vary
System.out.println(cpSet);
System.out.println(cpList);
}
/**
* @param nCol the supplier of the output collection
* @param cols the input array of collections
* @param <R> the type of the return collection
* @return the cartesian product of the multiple collections
*/
@SuppressWarnings("unchecked")
public static <R extends Collection<?>> R cartesianProduct(
Supplier nCol, Collection<?>... cols) {
// check if supplier is not null
if (nCol == null) return null;
return (R) Arrays.stream(cols)
// non-null and non-empty collections
.filter(col -> col != null && col.size() > 0)
// represent each element of a collection as a singleton collection
.map(col -> (Collection<Collection<?>>) col.stream()
.map(e -> Stream.of(e).collect(Collectors.toCollection(nCol)))
.collect(Collectors.toCollection(nCol)))
// summation of pairs of inner collections
.reduce((col1, col2) -> (Collection<Collection<?>>) col1.stream()
// combinations of inner collections
.flatMap(inner1 -> col2.stream()
// concatenate into a single collection
.map(inner2 -> Stream.of(inner1, inner2)
.flatMap(Collection::stream)
.collect(Collectors.toCollection(nCol))))
// collection of combinations
.collect(Collectors.toCollection(nCol)))
// otherwise an empty collection
.orElse((Collection<Collection<?>>) nCol.get());
}
Output (cropped, order may vary):
[[1, A, !], [1, !, B], [A, !, 2], [1, A, £], [1, !, C]...
[[1, A, $], [1, A, %], [1, A, £], [1, A, !], [1, B, $]...
See also: Finding cartesian product in Java