Cartesian product from 3 collections

Question

I need to do a Cartesian product from 3 lists. Here is the code.

XList<T> combine() {
    XList<T> returnList = new XList<>();

    List<T> list = new ArrayList(this.coll);
    List<T> a = (List<T>) list.get(0);
    List<T> b = (List<T>) list.get(1);
    List<T> c = (List<T>) list.get(2);

    //working
    //List<XList<T>> ll2 = a.stream()
    //        .flatMap(ai -> b.stream()
    //                .map(bi -> new XList<>(Arrays.asList(ai, bi))))
    //        .collect(Collectors.toList());

    // not working
    List<XList<T>> ll3 = a.stream()
            .flatMap(ai -> b.stream()
                    .flatMap(bi -> c.stream()
                            .map(ci -> new XList<>(Arrays.asList(ai, bi, ci)))))
            .collect(Collectors.toList());

    returnList.coll = (Collection<T>) ll3;

    return returnList;
}

When I try to do a Cartesian product from lists a and b it is working, but if I want to do it with a, b and c it retuns an empty list. What it's wrong? Thank you for reply.

score 0 · Answer 1 · 2021-08-08T13:06:07.710

You can generate a Cartesian product of multiple collections using three nested for-loops. Sequentially adding data from incoming collections to the intermediate result and obtaining the final result. Schematically, it looks like this:

res0: [[]]
col1: [1,2,3]
----
res1: [[1],[2],[3]]
col2: [4,5,6]
----
res2: [[1,4],[1,5],[1,6],[2,4],[2,5]...,[3,6]]
col3: [7,8,9]
----
res3: [[1,4,7],[1,4,8],[1,4,9],[1,5,7],[1,5,8]...,[3,6,9]]

Try it online!

/**
 * @param cols an arbitrary number of collections
 * @param <T>  the type of the elements
 * @return the Cartesian product
 */
@SafeVarargs
public static <T> List<List<T>> cartesianProduct(Collection<T>... cols) {
    // check if incoming data is not null
    if (cols == null) return Collections.emptyList();
    // Cartesian product, intermediate result
    List<List<T>> cp = Collections.singletonList(Collections.emptyList());
    // iterate through the incoming collections
    for (Collection<T> col : cols) {
        // non-null and non-empty collections
        if (col == null || col.size() == 0) continue;
        // intermediate result for next iteration
        List<List<T>> next = new ArrayList<>();
        // rows of current intermediate result
        for (List<T> row : cp) {
            // elements of current list
            for (T el : col) {
                // new row for next intermediate result
                List<T> nRow = new ArrayList<>(row);
                nRow.add(el);
                next.add(nRow);
            }
        }
        // pass to next iteration
        cp = next;
    }
    // Cartesian product, final result
    return cp;
}

public static void main(String[] args) {
    List<Integer> list1 = Arrays.asList(1, 2, 3);
    List<Integer> list2 = Arrays.asList(4, 5, 6);
    List<Integer> list3 = Arrays.asList(7, 8, 9);

    List<List<Integer>> cp = cartesianProduct(list1, list2, list3);
    // column-wise output
    int rows = 9;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cp.size(); j++)
            System.out.print(j % rows == i ? cp.get(j) + " " : "");
        System.out.println();
    }
}

Output:

[1, 4, 7] [2, 4, 7] [3, 4, 7] 
[1, 4, 8] [2, 4, 8] [3, 4, 8] 
[1, 4, 9] [2, 4, 9] [3, 4, 9] 
[1, 5, 7] [2, 5, 7] [3, 5, 7] 
[1, 5, 8] [2, 5, 8] [3, 5, 8] 
[1, 5, 9] [2, 5, 9] [3, 5, 9] 
[1, 6, 7] [2, 6, 7] [3, 6, 7] 
[1, 6, 8] [2, 6, 8] [3, 6, 8] 
[1, 6, 9] [2, 6, 9] [3, 6, 9]

^{See also: How to get Cartesian product from multiple lists?}

Cartesian product from 3 collections

1 Answers1

Linked