Consider an algorithm for obtaining a Cartesian product of multiple sets using three nested loops. The number of sets and their elements can be arbitrary. We multiply the sets sequentially and accumulate the result. The order does not matter, since the product does not change due to the permutation of the multipliers. As a result, the order will be different, but the combinations will be the same.
For clarity, let’s take several ordered sets:
a = [A,B,C,D]
b = [E,F,G]
c = [H,I]
d = [J]
The number of possible combinations is the product of the number of elements of all sets:
4 * 3 * 2 * 1 = 24
Let’s write a method in Java to solve such issues, we will use three nested for loops.
First, we prepare a list of lists List<List<T>>, filled with one empty value.
We will use it as an intermediate result and as a final result.
Then we pass through the received lists and sequentially supplement the intermediate result with their elements. At each step, we get a new intermediate result and move on. Thus, we consistently multiply pairs of lists and step-by-step accumulate the result.
Schematically, this process looks like this:
result0: [[]]
list1: [A,B,C,D]
--------
result1: [[A],[B],[C],[D]]
list2: [E,F,G]
--------
result2: [[A,E],[A,F],[A,G],[B,E],[B,F],...[D,G]]
list3: [H,I]
--------
result3: [[A,E,H],[A,E,I],[A,F,H],[A,F,I],[A,G,H],...[D,G,I]]
list4: [J]
--------
result4: [[A,E,H,J],[A,E,I,J],[A,F,H,J],[A,F,I,J],[A,G,H,J],...[D,G,I,J]]
Number of combinations: 24
[A, E, H, J] [B, E, H, J] [C, E, H, J] [D, E, H, J]
[A, E, I, J] [B, E, I, J] [C, E, I, J] [D, E, I, J]
[A, F, H, J] [B, F, H, J] [C, F, H, J] [D, F, H, J]
[A, F, I, J] [B, F, I, J] [C, F, I, J] [D, F, I, J]
[A, G, H, J] [B, G, H, J] [C, G, H, J] [D, G, H, J]
[A, G, I, J] [B, G, I, J] [C, G, I, J] [D, G, I, J]
The list can contain a modifiable number of elements. This simplifies the code.
/**
* @param lists an arbitrary number of lists
* @param <T> the type of elements in lists
* @return the Cartesian product of the passed lists
*/
public static <T> List<List<T>> cartesianProduct(List<List<T>> lists) {
// incoming data is not null
if (lists == null) return Collections.emptyList();
// intermediate result, contains one empty value
List<List<T>> cp = Collections.singletonList(Collections.<T>emptyList());
// pass through the received lists
for (List<T> list : lists) {
// non-null and non-empty lists
if (list == null || list.size() == 0) continue;
// next intermediate result
List<List<T>> next = new ArrayList<>();
// rows of the current intermediate result
for (List<T> row : cp) {
// elements of the current list
for (T el : list) {
// a new row for the next intermediate
// result, copy of the current row
List<T> nRow = new ArrayList<>(row);
// add the current element
nRow.add(el);
// add to the next intermediate result
next.add(nRow);
}
}
// update the intermediate result
cp = next;
}
// the final result
return cp;
}
// start the program and output the result
public static void main(String[] args) {
// an arbitrary number of lists and their elements
List<String> a = Arrays.asList("A", "B", "C", "D");
List<String> b = Arrays.asList("E", "F", "G");
List<String> c = Arrays.asList("H", "I");
List<String> d = Arrays.asList("J");
// cartesian product
List<List<String>> cp = cartesianProduct(Arrays.asList(a, b, c, d));
// output
System.out.println("Number of combinations: " + cp.size());
// combinations by columns
int rows = 6;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cp.size(); j++)
if (j % rows == i)
System.out.print(" " + cp.get(j));
System.out.println();
}
}
The output for this and the following code is the same, see above: combinations by columns.
The array contains a fixed number of elements. The code looks a little more complicated.
/**
* @param arrays an arbitrary number of arrays
* @param clazz the class of elements in arrays
* @param <T> the type of elements in arrays
* @return the Cartesian product of the passed arrays
*/
@SuppressWarnings("unchecked")
public static <T> T[][] cartesianProduct(Class<T> clazz, T[]... arrays) {
// incoming data is not null
if (clazz == null || arrays == null)
return (T[][]) Array.newInstance(clazz, 0, 0);
// intermediate result, contains one empty value
T[][] cp = (T[][]) Array.newInstance(clazz, 1, 0);
// pass through the received arrays
for (int a = 0; a < arrays.length; a++) {
// current array
T[] arr = arrays[a];
// non-null and non-empty array
if (arr == null || arr.length == 0) continue;
// next intermediate result, specify the number of rows
T[][] next = (T[][]) Array.newInstance(clazz,cp.length*arr.length,0);
// rows of the current intermediate result
for (int r = 0; r < cp.length; r++) {
// current row
T[] row = cp[r];
// elements of the current array
for (int e = 0; e < arr.length; e++) {
// current element
T el = arr[e];
// copy the current row into the new array [length + 1]
T[] nRow = Arrays.copyOf(row, row.length + 1);
// add the current element
nRow[row.length] = el;
// add to the next intermediate result
next[r * arr.length + e] = nRow;
}
}
// update the intermediate result
cp = next;
}
// the final result
return cp;
}
// start the program and output the result
public static void main(String[] args) {
// an arbitrary number of arrays and their elements
String[] a = {"A", "B", "C", "D"};
String[] b = {"E", "F", "G"};
String[] c = {"H", "I"};
String[] d = {"J"};
// cartesian product
String[][] cp = cartesianProduct(String.class, a, b, c, d);
// output
System.out.println("Number of combinations: " + cp.length);
// combinations by columns
int rows = 6;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cp.length; j++)
if (j % rows == i)
System.out.print(" " + Arrays.toString(cp[j]));
System.out.println();
}
}
The output for this and the previous code is the same, see above: combinations by columns.
© Golovin G.G., Code with comments, translation from Russian, 2021