将集合映射到所有组合的列表中

Question

我遇到了一个简单的任务.我想要做的是转变Map<K,Set<V>>为List<Map<K,V>>获得所有可能的组合:

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

预期结果:

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

对我感到羞耻,需要你的帮助.

为downvoters更新

我不是一个要求社区为我做家庭作业的学生,​​我不会问我是否真的需要帮助.好吧,原则上我会在符合条件的情况下尽快为这个问题分配全部代表奖金(800左右).

更新2

尊重我在之前的更新中的承诺,我开始了两个赏金的序列,其中最大的一个归于我的救世主,剩下的就是对其他可能的解决方案的奖励.

更新3

这是技术性的,交付承诺的消息(参见之前的更新).我要感谢所有SO社区在真正需要时提供帮助.非常特别感谢"Tudor"和"Ed Staub"及时参与和响应.第二个赏金将被分配到最优雅的解决方案,新人和每个人都有兴趣的好机会.

Answer 1

使用递归!因此,在递归的每个级别,您都会查看keyset()地图中的另一个键.您可以迭代地Set<V>将该键中的元素添加到要添加到列表中的当前地图.

你可以把它想象成一棵树.在根节点,您有一个空列表.然后树的每个后续级别i表示从该i组中选择哪个元素.

以下是代码以及包含测试用例的main方法:

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