Skip to content

Instantly share code, notes, and snippets.

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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment