Craig Craig - 2 months ago 16
Java Question

Cartesian product using Java Streams

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


Answer

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.