Map<Object, List<Object>>的组合

Question

Map<Object, List<Object>>的组合

4

我有一个 HashMap<GC，List<RR>>，其示例数据如下：

key   values

gc1 - rr1
    - rr2
    - rr3

gc2 - rr4
    - rr5

gc3 - rr6

我需要根据不同的GC，创建出所有可能的RR组合，例如：

Combination1: rr1, rr4, rr6
Combination2: rr1, rr5, rr6
Combination3: rr2, rr4, rr6
Combination4: rr2, rr5, rr6
Combination5: rr3, rr4, rr6
Combination6: rr3, rr5, rr6

到目前为止，我尝试的方法是按照 @Sanket Makani 的建议，将我的 HashMap<GC, List<RR>> 转换为 List<List<RR>>，然后像这样遍历所有元素：

List<List<RR>> inputList = new ArrayList<List<RR>>();

for (Map.Entry<GC, List<RR>> rrList : Map.entrySet()) {
    inputList.add(rrList.getValue());
}

List<List<RR>> combinationsList = new ArrayList<List<RR>>();

for (List<RR> rrList : inputList) {
    List<RR> rrList1 = new ArrayList<RR>();
    for (RR rr : rrList) {
        rrList1.add(rr);
    }
    combinationsList.add(rrList1);
}

这对我来说并不起作用，因为它会将所有的 RR 分组到一个 GC 中，如下：

Combination1: rr1, rr2, rr3
Combination2: rr4, rr5
Combination3: rr6

所以我的问题是，我该如何调整我的代码以获得期望的结果？

PS：不幸的是，我正在使用Java6，因此不允许使用Lambda/Stream。

PS2：我看到了类似的问题，但找不到我要找的确切示例。

编辑：

这是我根据@nandsito的答案最终实现的代码：

//this method groups RRs by GC key with a given list
HashMap<GC, List<RR>> GCRRHashMap = groupRRsByGC(list); 

List<Map.Entry<GC, List<RR>>> mapEntryList = new ArrayList<Map.Entry<GC, List<RR>>>(GCRRHashMap.entrySet());
List<List<RR>> combinationsList = new ArrayList<List<RR>>();
List<RR> combinations = new ArrayList<RR>();

generateCombinations(mapEntryList, combinations, combinationsList);



private void generateCombinations(
  List<Map.Entry<GC, List<RR>>> mapEntryList, 
  List<RR> combinations, List<List<RR>> combinationsList) {

  if (mapEntryList.isEmpty()) {
    combinationsList.add(new ArrayList<RoomStay>(combinations)); 
    return;
  }

  Map.Entry<GC, List<RR>> entry = mapEntryList.remove(0);

  List<RR> entryValue = new ArrayList<RR>(entry.getValue());

  while (!entryValue.isEmpty()) {

    RR rr = entryValue.remove(0);

    combinations.add(rr);

    generateCombinations(mapEntryList, combinations, combinationsList);

    combinations.remove(combinations.size() - 1);
  }

  mapEntryList.add(0, entry);

}

- Manuel S.

1

你可以将所有的列表存储在 List<List<RR>> 中，然后编写一个递归算法来打印所有的组合。或者你可以将所有的组合存储在 ArrayList<StringBuilder> 中，然后进行打印。 - Sanket Makani

@M.Prokhorov 我的第一个想法是通过Map.entrySet()进行迭代，然后在内部通过List进行迭代，但我认为这不起作用，因为我需要X个内部循环，就像我有键x值一样。 - Manuel S.

“that will not work” 和 “that will work very inefficiently” 之间有区别。 - M. Prokhorov

通过“我不认为这会起作用”我是指，“我猜可能有更好的解决方案来解决我的问题”。这是一个虚构的短语，抱歉意思可能会被误解。 - Manuel S.

组合：http://introcs.cs.princeton.edu/java/23recursion/Combinations.java.html - older coder

对于排列组合，我认为您想要的是：http://introcs.cs.princeton.edu/java/23recursion/Permutations.java.html - older coder

2个回答

1

你只需要通过递增的索引列表进行操作：

0,0,0
0,1,0
1,0,0
1,1,0
2,0,0
... etc.

很明显，你需要将这些行中的每一个转换为数据结构中的值。例如，0,0,0 映射到 rr1, rr4, rr6。这将涉及将映射转换为列表，以便索引一致。

这非常类似于普通的基数计数，其中你会增加最右边的列，如果它溢出，则将其设置为零并增加下一列。唯一的区别是每个列在不同的数字处溢出。

所以：

boolean increment(int[] indexes) {
   int column = 0;
   while(true) {
      indexes[column]++;
      if(indexes[column] <  numberOfRRsInColumn(column)) {
         return true;  // finished
      }
      indexes[column]=0;
      column++;
      if(column = indexes.length) {
         return false; // can't increment, no more.
      }
   }
}

这个实现将indexes[0]作为“最右侧”列。我略过了numberOfRRsInColumn()，但它应该很容易理解。

然后：

int[] indexes = new int[mapsize];
do {
    output(translate(map, indexes));
} while (increment(indexes));

- slim

你是指 translate(map, indexes) 的意思是什么？ - Manuel S.

@ManuelS. 这是我之前描述的从 [x,y,z] 到 data[0][x], data[1][y], data[2][z] 的转换，我称之为“应该很明显如何...”。有什么不够明显吗？ - slim

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nandsito · Accepted Answer

这里提供一种递归解决方案：

public static void main(String[] args) {

    // your data map
    Map<GC, List<RR>> map;

    // the map entry set as list, which will help
    // combining the elements
    //
    // note this is a modifiable list

    List<Map.Entry<GC, List<RR>>> mapEntryList =
            new ArrayList<Map.Entry<GC, List<RR>>>(map.entrySet());

    // the combinations list, which will store
    // the desired results

    List<RR> combinations = new ArrayList<RR>();

    doRecursion(mapEntryList, combinations);
}

private static void doRecursion(
        List<Map.Entry<GC, List<RR>>> mapEntryList,
        List<RR> combinations) {

    // end of recursion

    if (mapEntryList.isEmpty()) {

        // do what you wish
        //
        // here i print each element of the combination

        for (RR rr : combinations) {

            System.out.println(rr);
        }

        System.out.println();

        return;
    }

    // remove one GC from the entry list,
    // then for each RR from the taken GC
    //     put RR in the combinations list,
    //     call recursion
    //     the remove RR from the combinations list
    // end for each
    // then put GC back into its list

    Map.Entry<GC, List<RR>> entry = mapEntryList.remove(0);

    List<RR> entryValue = new ArrayList<RR>(entry.getValue());

    while (!entryValue.isEmpty()) {

        RR rr = entryValue.remove(0);

        combinations.add(rr);

        doRecursion(mapEntryList, combinations);

        combinations.remove(combinations.size() - 1);
    }

    mapEntryList.add(0, entry);
}