MAIN EN typewriter

older-tomato

Cartesian product of sets

Combinatorics • Direct product 07.09.2021

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]]

Combinations by columns #

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]

Cartesian product of lists #

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.

Cartesian product of arrays #

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