Skip to content

Instantly share code, notes, and snippets.

@ThomasPr
Created March 8, 2020 15:25
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Embed
What would you like to do?
Compute the Cartesian Product of many lists using Java Streams
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);
}
}
@sming
Copy link

sming commented May 18, 2022

This is excellent! Thank you.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment