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
).
Cartesian product of streams in Java 8 as stream (using streams only)
Passing the streams in your example is never better than passing Lists:
private static <T> Stream<T> cartesian(BinaryOperator<T> aggregator, List<T>... lists) {
...
}
And use it like this:
Stream<String> result = cartesian(
(a, b) -> a + b,
Arrays.asList("A", "B"),
Arrays.asList("K", "L"),
Arrays.asList("X", "Y")
);
In both cases you create an implicit array from varargs and use it as data source, thus the laziness is imaginary. Your data is actually stored in the arrays.
In most of the cases the resulting Cartesian product stream is much longer than the inputs, thus there's practically no reason to make the inputs lazy. For example, having five lists of five elements (25 in total), you will have the resulting stream of 3125 elements. So storing 25 elements in the memory is not very big problem. Actually in most of the practical cases they are already stored in the memory.
In order to generate the stream of Cartesian products you need to constantly "rewind" all the streams (except the first one). To rewind, the streams should be able to retrieve the original data again and again, either buffering them somehow (which you don't like) or grabbing them again from the source (colleciton, array, file, network, random numbers, etc.) and perform again and again all the intermediate operations. If your source and intermediate operations are slow, then lazy solution may be much slower than buffering solution. If your source is unable to produce the data again (for example, random numbers generator which cannot produce the same numbers it produced before), your solution will be incorrect.
Nevertheless totally lazy solution is possbile. Just use not streams, but stream suppliers:
private static <T> Stream<T> cartesian(BinaryOperator<T> aggregator,
Supplier<Stream<T>>... streams) {
return Arrays.stream(streams)
.reduce((s1, s2) ->
() -> s1.get().flatMap(t1 -> s2.get().map(t2 -> aggregator.apply(t1, t2))))
.orElse(Stream::empty).get();
}
The solution is interesting as we create and reduce the stream of suppliers to get the resulting supplier and finally call it. Usage:
Stream<String> result = cartesian(
(a, b) -> a + b,
() -> Stream.of("A", "B"),
() -> Stream.of("K", "L"),
() -> Stream.of("X", "Y")
);
result.forEach(System.out::println);
Cartesian product using Java Streams
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.
Stream of cartesian product of other streams, each element as a List?
A possible solution is as follows:
private static <T> Stream<List<T>> product(Stream<T>... streams) {
if (streams.length == 0) {
return Stream.empty();
}
List<List<T>> cartesian = streams[streams.length - 1]
.map(x -> Collections.singletonList(x))
.collect(Collectors.toList());
for (int i = streams.length - 2; i >= 0; i--) {
final List<List<T>> previous = cartesian;
cartesian = streams[i].flatMap(x -> previous.stream().map(p -> {
final List<T> list = new ArrayList<T>(p.size() + 1);
list.add(x);
list.addAll(p);
return list;
})).collect(Collectors.toList());
}
return cartesian.stream();
}
public static void main(String... args) {
final Stream<List<String>> result =
product(
Stream.of("A", "B", "C", "D"),
Stream.of("I", "J", "K"),
Stream.of("Y", "Z")
);
result.forEach(System.out::println);
}
The product-call returns a Stream<List<String>>
result which prints as
[A, I, Y]
[A, I, Z]
[A, J, Y]
[A, J, Z]
[A, K, Y]
[A, K, Z]
[B, I, Y]
[B, I, Z]
[B, J, Y]
[B, J, Z]
[B, K, Y]
[B, K, Z]
[C, I, Y]
[C, I, Z]
[C, J, Y]
[C, J, Z]
[C, K, Y]
[C, K, Z]
[D, I, Y]
[D, I, Z]
[D, J, Y]
[D, J, Z]
[D, K, Y]
[D, K, Z]
How to create a self join cartesian product of a set with java stream
Do below code:
Set<String> set = new HashSet<>(Arrays.asList("A", "B", "C"));
Set<String> cartesianSet = set
.stream()
.map(x-> set
.stream()
.map(y-> x+y)
.collect(Collectors.toSet()))
.flatMap(Collection::stream)
.collect(Collectors.toSet());
System.out.println(cartesianSet);//[AA, BB, CC, AB, BC, AC, CA, BA, CB]
Implement Cartesian product of several collections by Java Stream
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 Pair
s 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
Rewriting a Cartesian product using for loops using streams and lambdas in Java
You can use two flatMap
operations with a nested map
operation.
final List<String> statements = names.stream().flatMap(r->
likes.stream()
.flatMap(s -> dislikes.stream()
.map(t -> r + " likes " + s + " and dislikes " + t))
).collect(Collectors.toList());
Demo!
Create collection of cartesian product of two (and more) lists with Java Lambda
I'm having difficulty figuring out what you're hoping for, it looks like you're trying to get a Cartesian product? Like, given {1, 2}
and {3, 4}
, you're expecting {(1, 3), (1, 4), (2, 3), (2, 4)}
? (For what it's worth, I don't think that has any relationship to the mathematical definition of permutations, which generally involve different ways of ordering the contents of a single list.)
That could be written
xs.stream()
.flatMap(x -> ys.stream().map(y -> Pair.of(x, y)))
.collect(toList());
Related Topics
How to Emit and Handle Custom Events
Service Layer and Controller: Who Takes Care of What
Reverse Java Graphics2D Scaled and Rotated Coordinates
Spring Security 5:There Is No Passwordencoder Mapped for the Id "Null"
Java.Net.Connectexception :Connection Timed Out: Connect
Swing - Thread.Sleep() Stop Jtextfield.Settext() Working
Shuffle a List of Integers with Java 8 Streams API
How to Run a Class from Jar Which Is Not the Main-Class in Its Manifest File
How to Remove a Substring from a Given String
How to Get a Random Line of a Text File in Java
Java: Get Month Integer from Date
Superclass Reference Not Able to Call Subclass Method in Java
How to Get Which Jradiobutton Is Selected from a Buttongroup
How to Pause/Sleep/Wait in a Java Swing App