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

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

Answer 1

使用递归!因此，在递归的每个级别，您都会查看 keyset() 中的另一个键。的 map 。您在 Set<V> 中迭代添加元素对于要添加到列表中的当前 map 的那个键。

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

这是代码以及包含测试用例的主要方法:

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