Combinations of elements by columns

In a two-dimensional array, data is stored row-wise. Consider an algorithm for obtaining a Cartesian product by columns using three nested loops. The number of rows and columns can be arbitrary. We multiply the columns of the table sequentially and accumulate the result. The values do not necessarily have to be populated — we discard the null elements.

For example, let’s take a partially filled jagged two-dimensional array:

     | col1 | col2 | col3 | col4
-----|------|------|------|------
row1 | "A1" | "B1" | "C1" | "D1"
row2 | "A2" | "B2" | null | "D2"
row3 | "A3" | null | null | "D3"
row4 | "A4" | null |

The number of possible combinations is the product of the number of elements of all columns:

4 * 2 * 1 * 3 = 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 table columns, while they are present, — we consider the last column is the one after which all the elements are null. At each step, we supplement the intermediate result with the elements of the current column and get a new intermediate result. Thus, we consistently multiply columns and step-by-step accumulate the result.

Schematically, this process looks like this:

res0 * col1 = res1 * col2 = res2  * col3 = res3     * col4 = res4
-----|------|------|------|-------|------|----------|------|------------
[]   * A1   = A1   * B1   = A1,B1 * C1   = A1,B1,C1 * D1   = A1,B1,C1,D1
     * A2   = A2   * B2   = A1,B2 *      = A1,B2,C1 * D2   = A1,B1,C1,D2
     * A3   = A3   *      = A2,B1 *      = A2,B1,C1 * D3   = A1,B1,C1,D3
     * A4   = A4   *      = A2,B2 *      = A2,B2,C1 *      = A1,B2,C1,D1
     *      =      *      = A3,B1 *      = A3,B1,C1 *      = A1,B2,C1,D2
     *      =      *      = A3,B2 *      = A3,B2,C1 *      = A1,B2,C1,D3
     *      =      *      = A4,B1 *      = A4,B1,C1 *      = A2,B1,C1,D1
     *      =      *      = A4,B2 *      = A4,B2,C1 *      = A2,B1,C1,D2
     *      =      *      =       *      =          *      = A2,B1,C1,D3
     *      =      *      =       *      =          *      = A2,B2,C1,D1
     *      =      *      =       *      =          *      = ...........
     *      =      *      =       *      =          *      = ...........
     *      =      *      =       *      =          *      = A4,B2,C1,D3
-----|------|------|------|-------|------|----------|------|------------
1    * 4    = 4    * 2    = 8     * 1    = 8        * 3    = 24

Combinations by columns #

Number of combinations: 24
 [A1, B1, C1, D1] [A2, B1, C1, D1] [A3, B1, C1, D1] [A4, B1, C1, D1]
 [A1, B1, C1, D2] [A2, B1, C1, D2] [A3, B1, C1, D2] [A4, B1, C1, D2]
 [A1, B1, C1, D3] [A2, B1, C1, D3] [A3, B1, C1, D3] [A4, B1, C1, D3]
 [A1, B2, C1, D1] [A2, B2, C1, D1] [A3, B2, C1, D1] [A4, B2, C1, D1]
 [A1, B2, C1, D2] [A2, B2, C1, D2] [A3, B2, C1, D2] [A4, B2, C1, D2]
 [A1, B2, C1, D3] [A2, B2, C1, D3] [A3, B2, C1, D3] [A4, B2, C1, D3]

Cartesian product by columns #

The code will look simpler if you first transpose an array of arrays, but if this cannot be done, then in the outer loop, pass through the table columns as long as they are still exist.

/**
 * @param table the two-dimensional list
 * @param <T>   the type of elements in list
 * @return the Cartesian product of the elements by columns
 */
public static <T> List<List<T>> cartesianProduct(List<List<T>> table) {
    // incoming data is not null
    if (table == null) return Collections.emptyList();
    // intermediate result, contains one empty value
    List<List<T>> cp = Collections.singletonList(Collections.<T>emptyList());
    // columns are still present
    boolean notLast = true;
    // pass through the table columns, while they are present
    for (int i = 0; notLast; i++) {
        // there are no more columns
        notLast = false;
        // next intermediate result
        List<List<T>> next = new ArrayList<>();
        // pass through the combinations of the current intermediate result
        for (List<T> comb : cp) {
            // pass through the rows of the table
            for (List<T> row : table) {
                // if the column is still present and its value is also present
                if (row != null && i < row.size() && row.get(i) != null) {
                    // a new combination, copy the current combination
                    List<T> nComb = new ArrayList<>(comb);
                    // add the value from the column
                    nComb.add(row.get(i));
                    // add to the next intermediate result
                    next.add(nComb);
                    // columns are still present
                    notLast = true;
                }
            }
        }
        // if the columns are still present, then we update the intermediate
        // result and go to the next iteration, otherwise we exit the loop
        if (notLast) cp = next;
    }
    // the final result
    return cp;
}

// start the program and output the result
public static void main(String[] args) {
    // an arbitrary number of rows and their elements
    List<String> row1 = Arrays.asList("A1", "B1", "C1", "D1");
    List<String> row2 = Arrays.asList("A2", "B2", null, "D2");
    List<String> row3 = Arrays.asList("A3", null, null, "D3");
    List<String> row4 = Arrays.asList("A4", null);
    // jagged two-dimensional list
    List<List<String>> table = Arrays.asList(row1, row2, row3, row4);
    // cartesian product
    List<List<String>> cp = cartesianProduct(table);
    // 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 code see above: combinations by columns.