Created
March 8, 2020 15:25
-
-
Save ThomasPr/8e038d5ebca97261940bf1dd13d3417d to your computer and use it in GitHub Desktop.
Compute the Cartesian Product of many lists using Java Streams
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import static java.util.Collections.unmodifiableList; | |
| import static java.util.stream.Collectors.toList; | |
| import java.util.ArrayList; | |
| import java.util.List; | |
| import java.util.Objects; | |
| import java.util.function.BinaryOperator; | |
| import java.util.stream.Stream; | |
| public final class CartesianProductUtil { | |
| private CartesianProductUtil() { } | |
| /** | |
| * Compute the cartesian product for n lists. | |
| * The algorithm employs that A x B x C = (A x B) x C | |
| * | |
| * @param listsToJoin [a, b], [x, y], [1, 2] | |
| * @return [a, x, 1], [a, x, 2], [a, y, 1], [a, y, 2], [b, x, 1], [b, x, 2], [b, y, 1], [b, y, 2] | |
| */ | |
| public static <T> List<List<T>> cartesianProduct(List<List<T>> listsToJoin) { | |
| if (listsToJoin.isEmpty()) { | |
| return new ArrayList<>(); | |
| } | |
| listsToJoin = new ArrayList<>(listsToJoin); | |
| List<T> firstListToJoin = listsToJoin.remove(0); | |
| Stream<List<T>> startProduct = joinLists(new ArrayList<T>(), firstListToJoin); | |
| BinaryOperator<Stream<List<T>>> noOp = (a, b) -> null; | |
| return listsToJoin.stream() // | |
| .filter(Objects::nonNull) // | |
| .filter(list -> !list.isEmpty()) // | |
| .reduce(startProduct, CartesianProductUtil::joinToCartesianProduct, noOp) // | |
| .collect(toList()); | |
| } | |
| /** | |
| * @param products [a, b], [x, y] | |
| * @param toJoin [1, 2] | |
| * @return [a, b, 1], [a, b, 2], [x, y, 1], [x, y, 2] | |
| */ | |
| private static <T> Stream<List<T>> joinToCartesianProduct(Stream<List<T>> products, List<T> toJoin) { | |
| return products.flatMap(product -> joinLists(product, toJoin)); | |
| } | |
| /** | |
| * @param list [a, b] | |
| * @param toJoin [1, 2] | |
| * @return [a, b, 1], [a, b, 2] | |
| */ | |
| private static <T> Stream<List<T>> joinLists(List<T> list, List<T> toJoin) { | |
| return toJoin.stream().map(element -> appendElementToList(list, element)); | |
| } | |
| /** | |
| * @param list [a, b] | |
| * @param element 1 | |
| * @return [a, b, 1] | |
| */ | |
| private static <T> List<T> appendElementToList(List<T> list, T element) { | |
| int capacity = list.size() + 1; | |
| ArrayList<T> newList = new ArrayList<>(capacity); | |
| newList.addAll(list); | |
| newList.add(element); | |
| return unmodifiableList(newList); | |
| } | |
| } |
Hi there,
'java stream has already been operated upon or closed'. Please, can you point me a hint to overcome this issue ? I'am not a java expert
Usually means that the stream has been iterated, upon which, I believe (and I am rusty!) Java can close the stream so that it can be garbage collected. My advice would be to create 1 stream per thread which is a subset of the original stream. Just my 2d.
HTH
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hello Thomas and thank for you great work.
I would like to use your code to potentially generate millions and even billions of combinations.
So i introduce parallel stream instead of regular stream in methods 'cartesianProduct' and 'joinLists'. I have tried it but keeps getting the folowing error: 'java stream has already been operated upon or closed'. Please, can you point me a hint to overcome this issue ? I'am not a java expert