Map of sets into list of all combinations

Question

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'}
}

Shame on me, need your help.

update for downvoters

I'm not a student asking so-community to do my homework for me and I wouldn't be asking if I didn't really need help after pretty hard week. Well, on principle I'll assign all-rep bounty (800 or so) to this question as soon as it becomes eligible for it.

update 2

Respecting my promise in previous update, I start the sequence of two bounties with the biggest one going to my saviour, and the rest being the reward for other possible solutions.

update 3

This is technical, deliver-on-commitment message (see previous updates). I'd like to thank all the SO community for being helpful when it was really needed. Very special thanks are going to "Tudor" and "Ed Staub" for their timely participation and responsiveness. The second bounty will be assigned to the most elegant solution, good chance for newcomers and everyone interested.

Answer 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 );
        }
    }
}

Answer 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.