Generate all combinations of a Map of Lists into a List of Lists

Question

I have a Map<Integer, List<Float>> that represent a position with some scores, and I would like to generate all possible combinations of scores per position (essentially the cross-product of each list from the original map) into a List<List<Float>>. So let's say I have the following map:

{ 1 => [0.1f, 0.2f], 2 => [0.3f, 0.4f] }

I would to get the following list of lists of floats:

[[0.1f, 0.3f], [0.1f, 0.4f], [0.2f, 0.3f], [0.2f, 0.4f]]

I am pretty sure I have to use recursion, just not sure how to go on about it..

score 1 · Accepted Answer · edited Mar 20 '21 at 11:02

any time you have a recursive algorithm to code, you need an inductive definition to help design it.

base case: {} ↦ []
inductive step: M ↦ L ⇒ ( M ∪ { n ↦ S } ) ↦ L × S

For each element in S, you add it to the end of every list in L, and add the resulting list to your output.

List<List<Float>> llfNext = new LinkedList<List<Float>>();
for (float f : entEach.getValue())
    for (List<Float> lfEach : llfInductive)
        llfNext.add(copyAndAddToEnd(lfEach, f));
return llfNext;

It should be pretty easy from here, and then you can make it non-recursive and reduce some of the copying going on.

score 1 · Answer 2 · 2021-07-25T13:16:04.817

Using Java 9, you can generate all combinations of a Map of Lists into a List of Maps as follows.

Try it online!

Map<Integer, List<Float>> mapOfLists = new LinkedHashMap<>();
mapOfLists.put(1, List.of(0.1f, 0.2f));
mapOfLists.put(2, List.of(0.3f, 0.4f));
mapOfLists.put(3, List.of(0.5f, 0.6f));

List<Map<Integer, Float>> listOfMaps = mapOfLists.entrySet().stream()
        // Stream<List<Map<Integer,Float>>>
        .map(entry -> entry.getValue().stream()
                // represent list elements as Map<Integer,Float>
                .map(element -> Map.of(entry.getKey(), element))
                // collect a list of maps
                .collect(Collectors.toList()))
        // intermediate output
        //[{1=0.1}, {1=0.2}]
        //[{2=0.3}, {2=0.4}]
        //[{3=0.5}, {3=0.6}]
        .peek(System.out::println)
        // reduce a stream of lists to a single list
        // by sequentially multiplying the list pairs
        .reduce((list1, list2) -> list1.stream()
                // combinations of elements,
                // i.e. maps, from two lists
                .flatMap(map1 -> list2.stream()
                        .map(map2 -> {
                            // join entries of two maps
                            Map<Integer, Float> map =
                                    new LinkedHashMap<>();
                            map.putAll(map1);
                            map.putAll(map2);
                            return map;
                        }))
                // collect into a single list
                .collect(Collectors.toList()))
        .orElse(null);

// output a list of map values
listOfMaps.stream().map(Map::values).forEach(System.out::println);
//[0.1, 0.3, 0.5]
//[0.1, 0.3, 0.6]
//[0.1, 0.4, 0.5]
//[0.1, 0.4, 0.6]
//[0.2, 0.3, 0.5]
//[0.2, 0.3, 0.6]
//[0.2, 0.4, 0.5]
//[0.2, 0.4, 0.6]

^{See also: Convert a map of lists into a list of maps}

score 0 · Answer 3 · edited Mar 20 '21 at 11:00

List<List<Float>> finalList = new ArrayList<List<Float>>();
int pointsCounter = 0;
for (Integer key : map.keys()) {
    List<Float> scoresList = map.get(key);
    boolean firstValue = true;
    for (Float score : scoresList) {
        if (firstValue) {
            finalList.add(new ArrayList<Float>());
            firstValue = false;
        }
        finalList.get(pointsCounter).add(score);
    }
    pointsCounter++;
}

Generate all combinations of a Map of Lists into a List of Lists

3 Answers3