Implement Cartesian product of several collections by Java Stream

Question

Right now I can only implement the Cartesian product of two collections, here is the code:

public static <T1, T2, R extends Collection<Pair<T1, T2>>>
R getCartesianProduct(
        Collection<T1> c1, Collection<T2> c2,
        Collector<Pair<T1, T2>, ?, R> collector) {
    return c1.stream()
            .flatMap(e1 -> c2.stream().map(e2 -> new Pair<>(e1, e2)))
            .collect(collector);
}

This code works fine in IntelliJ, but not in Eclipse. Both with compiler compliance level of 1.8:

The method collect(Collector<? super Object,A,R>)
in the type Stream<Object> is not applicable for
the arguments (Collector<Pair<T1,T2>,capture#5-of ?,R>)

Here is Pair.java:

public class Pair<T1, T2> implements Serializable {
    protected T1 first;
    protected T2 second;
    private static final long serialVersionUID = 1360822168806852921L;

    public Pair(T1 first, T2 second) {
        this.first = first;
        this.second = second;
    }

    public Pair(Pair<T1, T2> pair) {
        this(pair.getFirst(), pair.getSecond());
    }

    public T1 getFirst() {
        return this.first;
    }

    public T2 getSecond() {
        return this.second;
    }

    public void setFirst(T1 o) {
        this.first = o;
    }

    public void setSecond(T2 o) {
        this.second = o;
    }

    public String toString() {
        return "(" + this.first + ", " + this.second + ")";
    }

    @Override
    public boolean equals(Object o) {
        if(!(o instanceof Pair))
            return false;
        Pair p = (Pair) o;
        if(!this.first.equals(p.first))
            return false;
        if(!this.second.equals(p.second))
            return false;
        return true;
    }

    @Override
    public int hashCode() {
        int hash = 1;
        hash = hash * 31 + this.first.hashCode();
        hash = hash * 31 + this.second.hashCode();
        return hash;
    }
}

How to fix this error?

Is there an elegant way to implement the Cartesian product of several collections? Suppose we have class tuple.

Answer 1

Eclipse has problems with type inference. If you add a type hint .<Pair<T1,T2>>flatMap, it compiles fine.

If I may suggest a different approach, consider making your cartesianProduct not do the entire stream and collection but merely be a helper for flatMap:

static <T1, T2, R> Function<T1, Stream<R>> crossWith(
         Supplier<? extends Stream<T2>> otherSup, 
         BiFunction<? super T1, ? super T2, ? extends R> combiner
) {
    return t1 -> otherSup.get().map(t2 -> combiner.apply(t1, t2));
}

Now you only need to create a Pair if you want the result to contains Pairs and you can do a higher-order cartesian product by applying flatMap several times:

List<String> letters = Arrays.asList("A", "B", "C");
List<Integer> numbers = Arrays.asList(1, 2, 3);

List<Pair<String, Integer>> board = letters.stream()
                .flatMap(crossWith(numbers::stream, Pair::new))
                .collect(toList());


List<String> ops = Arrays.asList("+", "-", "*", "/");

List<String> combinations = letters.stream()
                .flatMap(crossWith(ops::stream, String::concat))
                .flatMap(crossWith(letters::stream, String::concat))
                .collect(toList());   // triple cartesian product

Answer 2

Here's a solution that generalizes to the case that the number of requisite flatMap-applications (i. e. the order of the product) is not known at compile time.

BinaryOperator<Function<String,Stream<String>>> kleisli = (f,g) -> s -> f.apply(s).flatMap(g);

List<String> cartesian(int n, Collection<String> coll) {
    return coll.stream()
           .flatMap( IntStream.range(1, n).boxed()
                     .map(_any -> crossWith(coll::stream, String::concat)) // create (n-1) appropriate crossWith instances
                     .reduce(s -> Stream.of(s), kleisli)                   // compose them sequentially
                    )                                                      // flatMap the stream with the entire function chain
           .collect(toList());
}

You'll find details of how this works at my own blog.

Answer 3

You can use Supplier as a parameter for the Collectors.toCollection method. This simplifies the code and makes it more generic. The Cartesian product of different types and numbers of collections and their elements.

Try it online!

public static void main(String[] args) {
    Set<Integer> a = Set.of(1, 2);
    Set<Character> b = Set.of('*', '+');
    List<String> c = List.of("A", "B");

    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 (order may vary):

[[1,A,*],[1,B,*],[1,A,+],[A,2,*],[1,B,+],[2,B,*],[A,2,+],[2,B,+]]
[[2,+,A],[2,+,B],[2,*,A],[2,*,B],[1,+,A],[1,+,B],[1,*,A],[1,*,B]]

---

^{See also the less generic version: Finding cartesian product in Java}