Instantly share code, notes, and snippets.

# ThomasPr/CartesianProductUtil.java

Created March 8, 2020 15:25
Show Gist options
• 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 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 List> cartesianProduct(List> listsToJoin) { if (listsToJoin.isEmpty()) { return new ArrayList<>(); } listsToJoin = new ArrayList<>(listsToJoin); List firstListToJoin = listsToJoin.remove(0); Stream> startProduct = joinLists(new ArrayList(), firstListToJoin); BinaryOperator>> 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 Stream> joinToCartesianProduct(Stream> products, List 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 Stream> joinLists(List list, List toJoin) { return toJoin.stream().map(element -> appendElementToList(list, element)); } /** * @param list [a, b] * @param element 1 * @return [a, b, 1] */ private static List appendElementToList(List list, T element) { int capacity = list.size() + 1; ArrayList newList = new ArrayList<>(capacity); newList.addAll(list); newList.add(element); return unmodifiableList(newList); } }

### sming commented May 18, 2022

This is excellent! Thank you.