'Map of sets into list of all combinations

I'm stuck with a simple task. What I want to do is to transform Map<K,Set<V>> into the List<Map<K,V>> getting all possible combinations:

Map {
  {'k1' => set{'v11', 'v12'}},
  {'k2' => set{'v21', 'v22', 'v23'}},
  {'k3' => set{'v31'}}
}

Expected result:

List
{
  Map{'k1'=>'v11', 'k2'=>'v21', 'k3'=>'v31'}, 
  Map{'k1'=>'v11', 'k2'=>'v22', 'k3'=>'v31'},  
  Map{'k1'=>'v11', 'k2'=>'v23', 'k3'=>'v31'}, 
  Map{'k1'=>'v12', 'k2'=>'v21', 'k3'=>'v31'}, 
  Map{'k1'=>'v12', 'k2'=>'v22', 'k3'=>'v31'}, 
  Map{'k1'=>'v12', 'k2'=>'v23', 'k3'=>'v31'}
}

Solution 1:^[1]

Use recursion! So at each level of the recursion, you look at another key in the keyset() of the map. You add iteratively add elements in the Set<V> for that key to the current map that you want to add to the list.

You can think of this as a tree. At the root node, you have an empty list. Then each subsequent level of the tree i represents a choice of which element to take from the ith set.

Here is the code along with a main method containing a test case:

import java.util.*;

public class Test {
    // method called to generate combinations using map, putting the combinations in list
    public static <K,V> void combinations( Map<K,Set<V>> map, List<Map<K,V>> list ) {
        recurse( map, new LinkedList<K>( map.keySet() ).listIterator(), new HashMap<K,V>(), list );
    }

    // helper method to do the recursion
    private static <K,V> void recurse( Map<K,Set<V>> map, ListIterator<K> iter, Map<K,V> cur, List<Map<K,V>> list ) {
            // we're at a leaf node in the recursion tree, add solution to list
        if( !iter.hasNext() ) {
            Map<K,V> entry = new HashMap<K,V>();

            for( K key : cur.keySet() ) {
                entry.put( key, cur.get( key ) );
            }

            list.add( entry );
        } else {
            K key = iter.next();
            Set<V> set = map.get( key );

            for( V value : set ) {
                cur.put( key, value );
                recurse( map, iter, cur, list );
                cur.remove( key );
            }

            iter.previous();
        }
    }

    public static void main( String[] args ) {
        Map<Integer,Set<Integer>> map = new HashMap<Integer,Set<Integer>>() {{
            put( 1, new HashSet<Integer>() {{
                add( 11 );
                add( 12 );
            }} );
            put( 2, new HashSet<Integer>() {{
                add( 21 );
                add( 22 );
                add( 23 );
            }} );
            put( 3, new HashSet<Integer>() {{
                add( 31 );
            }} );
        }};
        List<Map<Integer,Integer>> list = new LinkedList<Map<Integer,Integer>>();
        combinations( map, list );

        for( Map<Integer,Integer> combination : list ) {
            System.out.println( combination );
        }
    }
}

Solution 2:^[2]

Hint: use recursion to generate a combination "tree".

Edit: Ok, I had some free time and decided to give it shot:

/**
 * 
 * @param <K> The type of the key
 * @param <V> The type of the value
 * @param index The index of the current key to inspect
 * @param current The current map being built by recursion
 * @param map The original input
 * @param list The result
 */ 
public static <K, V> void Combine(int index, Map<K, V> current, 
                                  Map<K, Set<V>> map, 
                                  List<Map<K, V>> list) {
    
    if(index == map.size()) { // if we have gone through all keys in the map
        Map<K, V> newMap = new HashMap<K, V>();
        System.out.println(current);
        for(K key: current.keySet()) {          // copy contents to new map.    
            newMap.put(key, current.get((K)key));               
        }           
        list.add(newMap); // add to result.
    } else {
        Object currentKey = map.keySet().toArray()[index]; // take the current key
        for(V value: map.get(currentKey)) {
            current.put((K)currentKey, value); // put each value into the temporary map
            Combine(index + 1, current, map, list); // recursive call
            current.remove(currentKey); // discard and try a new value
        }
    }
}

I've tested on a few cases and I think it's correct. Let me know. You can call this from another method that only takes map as input, creates the default parameters index, current and list and returns list as output.

Edit Small Java 8+ Update

public static <K, V> void combine(int index, Map<K, V> current, Map<K, List<V>> map, List<Map<K, V>> list) {

    if (index == map.size()) { // if we have gone through all keys in the map
        System.out.println(current);
        list.add(new HashMap<>(current)); // add to result.
    } else {
        K currentKey = map.keySet().stream().skip(index).findFirst().get(); // take the current key
        for (V value : map.get(currentKey)) {
            current.put(currentKey, value); // put each value into the temporary map
            combine(index + 1, current, map, list); // recursive call
            current.remove(currentKey); // discard and try next value
        }
    }
}

Solution 3:^[3]

VERY updated.

Here's a solution for Guava-heads. It should be pretty easy to convert if Guava's not your thing. This one is not recursive. It outputs a list of pairs of string-pairs, which I think is what you really want.

static ImmutableMap<String,ImmutableSet<String>> input = ImmutableMap.of(
    "k1", ImmutableSet.of("v11", "v12"),
    "k2", ImmutableSet.of("v21", "v22", "v23"),
    "k3", ImmutableSet.of("v31", "v32", "v33", "v34"));

static class Pair<T,U>
{
    T left;        U right;
    static <T,U> Pair of(T l, U r)
    {   return new Pair(l, r);      }
    Pair(T l, U r)    { left = l; right = r; }
}

static List<Pair<Pair<String, String>,Pair<String, String>>> transform(Map<String,ImmutableSet<String>> input)
{
    List<Pair<Pair<String, String>,Pair<String, String>>> output = Lists.newArrayList();
    // Not a real copy - very cheap.
    ImmutableList<Map.Entry<String, ImmutableSet<String>>> entryList = ImmutableList.copyOf(input.entrySet());
    for ( int i = 0; i < entryList.size(); i++ )
    {
        final Map.Entry<String, ? extends Set<String>> leftEntry = entryList.get(i);
        for ( int j = i+1; j < entryList.size(); j++ )
        {
            final Map.Entry<String, ? extends Set<String>> rightEntry = entryList.get(j);
            for ( String v1 : leftEntry.getValue() )
                for ( String v2 : rightEntry.getValue() )
                    output.add(Pair.of(
                        Pair.of(leftEntry.getKey(), v1),
                        Pair.of(rightEntry.getKey(), v2)));
        }

    }
    return output;
}

Solution 4:^[4]

First thank you for the case and the provided implementations! We got across the same issue, and saved us a ton of time to see them! We leave a python implementation, for those who may deal with the same issue but in another language :)

def combinations(themap, maplist):
    return recurse(themap, themap.keys(), {}, maplist, 0)

def recurse(themap, iterator, curmap, maplist, iteratoridx):
    if(iteratoridx>=len(iterator)):
        entry = {}
        for key in curmap.keys():
            entry[key]=curmap[key]
        maplist.append(entry)
    else:
        key = iterator[iteratoridx]
        theset = themap.get(key)
        for value in theset:
            curmap[key]=value
            recurse(themap, iterator, curmap, maplist, iteratoridx+1)
            curmap.pop(key, None)
        iteratoridx=iteratoridx-1


maplist=[]
grid={"A":[1, 2, 3], "B":[4, 5, 6], "C":[7, 8, 9]}
combinations(grid, maplist)
print(maplist)

Solution 5:^[5]

suppose we have the variable "source" from the type Map<K,Set<V>> to transform source to the required type you can use the next code:

List<Map<K,V>> target = new ArrayList<Map<K,V>>();
for(K key : source.keySet()){
    Map<K,V> map = new HashMap<K, V>();
    for(V val : source.get(key)){
       map.put(key, val)
    }
    target.add(map);
}

Solution 6:^[6]

List<Map<K,V>> target = new ArrayList<Map<K,V>>();
for(K key : source.keySet()){
    for(V val : source.get(key)){
       Map<K,V> map = new HashMap<K, V>();
       map.put(key, val)
       target.add(map);
    }
}

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution	Source
Solution 1
Solution 2	snukluck
Solution 3
Solution 4
Solution 5	Eihab Khadora
Solution 6	Fantius

'Map of sets into list of all combinations

Solution 1:[1]

Solution 2:[2]

Solution 3:[3]

Solution 4:[4]

Solution 5:[5]

Solution 6:[6]