How do I generate a Cartesian product in Java?

Question

I have a number of ArrayList with each ArrayList having objects and each one can have different length. I need to generate permutation like in the below example:

Suppose I have 2 ArrayList:

ArrayList A has object a, object b and object c
ArrayList B has object d, object e

Then the output should be 6 new ArrayList with these combinations:

Combination 1 object a and object d,
Combination 2 object a and object e,
Combination 3 object b and object d,
Combination 4 object b and object e,
Combination 5 object c and object d,
Combination 6 object c and object e,

Can anyone help me?

Answer 1

Guava 19+

Lists.cartesianProduct(List...)

E.g.:

List<Object> list1 = Arrays.asList("a", "b", "c");
List<Object> list2 = Arrays.asList("d", "e");
System.out.println(Lists.cartesianProduct(list1, list2));

Output:

[[a, d], [a, e], [b, d], [b, e], [c, d], [c, e]]

Answer 2

Cartesian product of multiple lists using the map and reduce approach

• The map method represents each element of the list as a singleton list and specifies the format of the result.

  Intermediate output:

  [[a], [b], [c]]
  [[d], [e]]
  [[f]]
  

• The reduce method sums pairs of 2D lists into a single 2D list.

  Final output:

  [[a, d, f], [a, e, f], [b, d, f], [b, e, f], [c, d, f], [c, e, f]]
  

Try it online!

public static void main(String[] args) {
    List<String> a = Arrays.asList("a", "b", "c");
    List<String> b = Arrays.asList("d", "e");
    List<String> c = Arrays.asList("f");

    List<List<String>> cp = cartesianProduct(Arrays.asList(a, b, c));
    // output
    System.out.println(cp);
}

public static <T> List<List<T>> cartesianProduct(List<List<T>> lists) {
    // check if not null
    if (lists == null) return null;
    // cartesian product of multiple lists
    return lists.stream()
            // only those lists that are not null and not empty
            .filter(list -> list != null && list.size() > 0)
            // represent each list element as a singleton list
            .map(list -> list.stream().map(Collections::singletonList)
                    // Stream<List<List<T>>>
                    .collect(Collectors.toList()))
            // intermediate output
            .peek(System.out::println)
            // stream of lists into a single list
            .reduce((lst1, lst2) -> lst1.stream()
                    // combinations of inner lists
                    .flatMap(inner1 -> lst2.stream()
                            // concatenate into a single list
                            .map(inner2 -> Stream.of(inner1, inner2)
                                    .flatMap(List::stream)
                                    .collect(Collectors.toList())))
                    // list of combinations
                    .collect(Collectors.toList()))
            // otherwise an empty list
            .orElse(Collections.emptyList());
}

---

^{See also: Cartesian product of an arbitrary number of sets}