Cartesian product using Java Streams

Question

I have a cartesian product function in JavaScript:

function cartesianProduct(arr) {
    return arr.reduce(function(a,b) {
        return a.map(function(x) {
            return b.map(function(y) {
                return x.concat(y);
            });
        }).reduce(function(a,b) { return a.concat(b); }, []);
    }, [[]]);
}

So that if I have a 3D array:

var data = [[['D']], [['E'],['L','M','N']]];

The result of cartesianProduct(data) would be the 2D array:

[['D','E'], ['D','L','M','N']]

What I'm trying to do is write this cartesian product function in Java using Streams.

So far I have the following in Java:

public Collection<Collection<String>> cartesianProduct(Collection<Collection<Collection<String>>> arr) {

    return arr.stream().reduce(new ArrayList<Collection<String>>(), (a, b) -> {
        return a.stream().map(x -> {
            return b.stream().map(y -> {
                return Stream.concat(x.stream(), y.stream());
            });
        }).reduce(new ArrayList<String>(), (c, d) -> {
            return Stream.concat(c, d);
        });
    });
}

I have a type checking error that states:

ArrayList<String> is not compatible with Stream<Stream<String>>

My guesses as to what is wrong:

I need to use a collector somewhere (maybe after the Stream.concat)
The data type for the identity is wrong

Refer to http://stackoverflow.com/questions/32131987/how-can-i-make-cartesian-product-with-java-8-streams or http://stackoverflow.com/questions/32631602/cartesian-product-of-streams-in-java-8-as-stream-using-streams-only — Tunaki, Jul 27 '16 at 22:45
I don't think a Stream is the right model here. A Stream takes elements of a single list/set/pool/whatever and does something with them. But you're trying to take elements from two separate entities and combining them in a specific way. You can use lambda expressions to represent all of your JavaScript closures, but I don't think a Stream is the right tool. — Bobulous, Jul 29 '16 at 20:51
@michaelsnowden It's an attempt to implement a cross product function using Java streams. Do you have anything of actual value to add to the discussion or are you still confused? — Craig, Aug 02 '16 at 17:29
@Bobulous The more I've learned about Streams this past week the more I'm coming to this realization. I think I'm treating Streams too much like closures in functional programming. — Craig, Aug 02 '16 at 17:34
@michaelsnowden unless your pointing out my error in calling it a cross product rather than a Cartesian product? — Craig, Aug 02 '16 at 17:35
@Craig Oh, I see. You're doing an n-ary Cartesian product. It would help to clarify that in your question because "cross product" usually means "vector cross product" and the Cartesian product is usually between two sets, not n sets. Perhaps you should edit your question with this clarification. — michaelsnowden, Aug 02 '16 at 18:04

score 2 · Accepted Answer · answered Aug 04 '16 at 03:52

This is possible with a bit of functional programming magic. Here's method which accepts Collection<Collection<Collection<T>>> and produces Stream<Collection<T>>:

static <T> Stream<Collection<T>> cartesianProduct(Collection<Collection<Collection<T>>> arr)
{
    return arr.stream()
        .<Supplier<Stream<Collection<T>>>> map(c -> c::stream)
        .reduce((s1, s2) -> () -> s1.get().flatMap(
                a -> s2.get().map(b -> Stream.concat(a.stream(), b.stream())
                        .collect(Collectors.toList()))))
        .orElseGet(() -> () -> Stream.<Collection<T>>of(Collections.emptyList()))
        .get();
}

Usage example:

cartesianProduct(
    Arrays.asList(Arrays.asList(Arrays.asList("D")),
        Arrays.asList(Arrays.asList("E"), Arrays.asList("L", "M", "N"))))
            .forEach(System.out::println);

Output:

[D, E]
[D, L, M, N]

Of course instead of .forEach() you can collect the results to the List if you want to return Collection<Collection<T>> instead, but returning Stream seems more flexible to me.

A bit of explanation:

Here we create a stream of stream suppliers via map(c -> c::stream). Each function of this stream may produce by demand a stream of the corresponding collection elements. We do this because streams a once off (otherwise having stream of streams would be enough). After that we reduce this stream of suppliers creating a new supplier for each pair which flatMaps two streams and maps their elements to the concatenated lists. The orElseGet part is necessary to handle the empty input. The last .get() just calls the final stream supplier to get the resulting stream.

Cartesian product using Java Streams

1 Answers1