Skip to content

Instantly share code, notes, and snippets.

@ThomasPr
Created March 8, 2020 15:25
Show Gist options
  • Save ThomasPr/8e038d5ebca97261940bf1dd13d3417d to your computer and use it in GitHub Desktop.
Save ThomasPr/8e038d5ebca97261940bf1dd13d3417d to your computer and use it in GitHub Desktop.
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