我遇到了一个简单任务的难题。我想要做的是将 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'}
}
keyset()中的另一个键。您将按迭代方式向要添加到列表中的当前地图中添加该键的 Set<V>中的元素。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 );
}
}
}
Map<K1,Map<K2,V>>），现在它完美地工作了。谢谢。 - Robert Hume/**
*
* @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
}
}
}
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
}
}
}
非常更新。
下面是一个针对Guava开发者的解决方案。如果你不熟悉Guava，也很容易转换成其他工具。这个方案不是递归的。它输出了一组字符串对的列表，我觉得这正是你想要的。
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;
}
{k1->v11, k2-v22, k3->v32, ...}。您的代码生成了正确的组合，我会再多试一下，但此时我无法理解这里出现一对对的原因 :( - andbi首先感谢您提供的案例和实现！我们遇到了同样的问题，看到它们为我们节省了大量时间！我们留下了一个Python实现，供那些可能在其他语言中处理相同问题的人使用 :)
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)
Map<K,Set<V>>的变量“source”，要将其转换为所需的类型，您可以使用以下代码：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);
}
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);
}
}