How can I make Cartesian product with Java 8 streams?

Solution 1:

You can solve this using the recursive flatMap chain.

First as we need to move back and forth by the map values, it's better to copy them to the ArrayList (this is not the deep copy, in your case it's ArrayList of 3 elements only, so the additional memory usage is low).

Second, to maintain a prefix of previously visited elements, let's create a helper immutable Prefix class:

private static class Prefix<T> {
    final T value;
    final Prefix<T> parent;

    Prefix(Prefix<T> parent, T value) {
        this.parent = parent;
        this.value = value;
    }

    // put the whole prefix into given collection
    <C extends Collection<T>> C addTo(C collection) {
        if (parent != null)
            parent.addTo(collection);
        collection.add(value);
        return collection;
    }
}

This is very simple immutable linked list which can be used like this:

List<String> list = new Prefix<>(new Prefix<>(new Prefix<>(null, "a"), "b"), "c")
                          .addTo(new ArrayList<>()); // [a, b, c];

Next, let's create the internal method which chains flatMaps:

private static <T, C extends Collection<T>> Stream<C> comb(
        List<? extends Collection<T>> values, int offset, Prefix<T> prefix,
        Supplier<C> supplier) {
    if (offset == values.size() - 1)
        return values.get(offset).stream()
                     .map(e -> new Prefix<>(prefix, e).addTo(supplier.get()));
    return values.get(offset).stream()
            .flatMap(e -> comb(values, offset + 1, new Prefix<>(prefix, e), supplier));
}

Looks like recursion, but it's more complex: it doesn't call itself directly, but passed lambda which calls the outer method. Parameters:

• values: the List of original values (new ArrayList<>(map.values) in your case).
• offset: the current offset within this list
• prefix: the current prefix of length offset (or null if offset == 0). It contains currently selected elements from the collections list.get(0), list.get(1) up to list.get(offset-1).
• supplier: the factory method to create the resulting collection.

When we reached the end of the values list (offset == values.size() - 1), we map the elements of the last collection from the values to the final combination using the supplier. Otherwise we use the flatMap which for each intermediate element enlarges the prefix and calls the comb method again for the next offset.

Finally here's public method to use this feature:

public static <T, C extends Collection<T>> Stream<C> ofCombinations(
        Collection<? extends Collection<T>> values, Supplier<C> supplier) {
    if (values.isEmpty())
        return Stream.empty();
    return comb(new ArrayList<>(values), 0, null, supplier);
}

A usage example:

Map<String, Collection<String>> map = new LinkedHashMap<>(); // to preserve the order
map.put("A", Arrays.asList("a1", "a2", "a3", "a4"));
map.put("B", Arrays.asList("b1", "b2", "b3"));
map.put("C", Arrays.asList("c1", "c2"));

ofCombinations(map.values(), LinkedHashSet::new).forEach(System.out::println);

We collect individual combinations to the LinkedHashSet again to preserve the order. You can use any other collection instead (e.g. ArrayList::new).

Solution 2:

A solution that mainly operates on lists, making things a lot simpler. It does a recursive call in flatMap, keeping track of the elements that have already been combined, and the collections of elements that are still missing, and offers the results of this nested recursive construction as a stream of lists:

import java.util.*;
import java.util.stream.Stream;

public class CartesianProduct {
    public static void main(String[] args) {
        Map<String, Collection<String>> map =
                new LinkedHashMap<String, Collection<String>>();
        map.put("A", Arrays.asList("a1", "a2", "a3", "a4"));
        map.put("B", Arrays.asList("b1", "b2", "b3"));
        map.put("C", Arrays.asList("c1", "c2"));
        ofCombinations(map.values()).forEach(System.out::println);
    }

    public static <T> Stream<List<T>> ofCombinations(
            Collection<? extends Collection<T>> collections) {
        return ofCombinations(
                new ArrayList<Collection<T>>(collections),
                Collections.emptyList());
    }

    private static <T> Stream<List<T>> ofCombinations(
            List<? extends Collection<T>> collections, List<T> current) {
        return collections.isEmpty() ? Stream.of(current) :
                collections.get(0).stream().flatMap(e -> {
                    List<T> list = new ArrayList<T>(current);
                    list.add(e);
                    return ofCombinations(
                            collections.subList(1, collections.size()), list);
                });
    }
}