How can I make Cartesian product with Java 8 streams?
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
ifoffset == 0
). It contains currently selected elements from the collectionslist.get(0)
,list.get(1)
up tolist.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
).
A simpler answer, for a simpler situation where you just want to have the cartesian product of the elements of two collections.
Here's some code which uses flatMap
to generate the cartesian product of two short lists:
public static void main(String[] args) {
List<Integer> aList = Arrays.asList(1, 2, 3);
List<Integer> bList = Arrays.asList(4, 5, 6);
Stream<List<Integer>> product = aList.stream().flatMap(a ->
bList.stream().flatMap(b ->
Stream.of(Arrays.asList(a, b))));
product.forEach(p -> { System.out.println(p); });
// prints:
// [1, 4]
// [1, 5]
// [1, 6]
// [2, 4]
// [2, 5]
// [2, 6]
// [3, 4]
// [3, 5]
// [3, 6]
}
If you want to add more collections, just nest the streams a litter further:
aList.stream().flatMap(a ->
bList.stream().flatMap(b ->
cList.stream().flatMap(c ->
Stream.of(Arrays.asList(a, b, c)))));
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);
});
}
}
Cartesian product in Java 8 with forEach:
List<String> listA = Arrays.asList("0", "1");
List<String> listB = Arrays.asList("a", "b");
List<String> cartesianProduct = new ArrayList<>();
listA.forEach(a -> listB.forEach(b -> cartesianProduct.add(a + b)));
System.out.println(cartesianProduct);
// Output: [0a, 0b, 1a, 1b]