Cartesian product of map values

Question

I have map like below:

{"A" : ["A1", "A2", "A3"], "B" : ["B1", "B2", "B3"]}

And I would like to get data like below:

A1, B1
A1, B2
A1, B3
A2, B1
A2, B2
...

I tried like below:

for (String aKey : map.get("A"))
    for (String bKey : map.get("B"))
        // work with aKey + bKey

But it is not code that I want since map data is dynamic and unexpectable.

So I should get map data like below but cannot make it as I want:

for (String key : map.keySet())
    for (String values : map.get(key))
        // unable to make data I want

score 0 · Answer 1 · answered Oct 15 '19 at 21:39

you have correctly understood that you cannot create a cartesian product of arbitrary data with a static set of nested loops. what you need is a dynamic set of nested loops. i assume you tried that with your last code snippet. it seems you also understood that you need as many nested loops as there are sets in the data. the question remains: how to program a dynamic number of nested loops.

basically there are two ways to do a dynamic number of nested loops: recursive and iterative. both achieve the same result and the performance (in terms of time and memory) should be similar. if implemented well that is.

here are two similar questions one explicitly asking for a iterative solution:

try to understand both. your brain might prefer one over the other but it is worth it to at least understand both.

bonus question for the recursive approach because recursion is, arguably, harder to understand: Simulating nested loops

score 0 · Answer 2 · 2021-07-25T22:30:37.503

If you have a map of lists, you can obtain a Cartesian product of its values using the map and reduce approach. This code can be used with an arbitrary number of lists.

Try it online!

// a map of lists
Map<String, List<String>> map = new TreeMap<>();
map.put("A", Arrays.asList("A1", "A2"));
map.put("B", Arrays.asList("B1", "B2"));
map.put("C", Arrays.asList("C1", "C2"));

// cartesian product of the map values
List<List<String>> cp = map.values().stream()
        // represent each element of a list as a singleton list
        .map(list -> list.stream().map(Arrays::asList)
                // Stream<List<List<String>>>
                .collect(Collectors.toList()))
        // summation of pairs of list into a single list
        .reduce((list1, list2) -> list1.stream()
                // combinations of inner lists
                .flatMap(inner1 -> list2.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());

// output
map.forEach((k, v) -> System.out.println(k + ": " + v));
cp.forEach(System.out::println);

Output:

A: [A1, A2]
B: [B1, B2]
C: [C1, C2]
[A1, B1, C1]
[A1, B1, C2]
[A1, B2, C1]
[A1, B2, C2]
[A2, B1, C1]
[A2, B1, C2]
[A2, B2, C1]
[A2, B2, C2]

^{See also: How to create cartesian product over arbitrary groups of numbers in Java?}

Cartesian product of map values

2 Answers2

Linked