Clever Geek Handbook

Map Combinations <Object, List <Object >>

I have HashMap<GC, List<RR>>

with example data, for example:

key   values

gc1 - rr1
    - rr2
    - rr3

gc2 - rr4
    - rr5

gc3 - rr6

And I need to create all possible combinations of RRs from different GCs, for example:

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

What I've tried so far, as @Sanket Makani suggests, turn mine HashMap<GC, List<RR>>

into List<List<RR>>

and then iterate over all elements like:

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

This doesn't work for me as it groups all RRs inside one GC, like this:

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

So my quesiton is: how can I adapt my code to get the expected result?

PS: I'm working with Java6 unfortunately that's why lambdas / streams are not allowed.

PS2: I've seen similar questions but can't find an exact example of what I'm looking for either.

EDIT:

This is my final implementation, with @ nandsito's answer:

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

}
+3


source share


2 answers


Here's a recursive solution:



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


source


All you really need to do is work with an incremental list of indices:

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

It should be obvious how to translate each of these strings into values ​​from your data structure. for example is 0,0,0

displayed on rr1, rr4, rr6

. This will involve converting the map to a list to keep the indexes consistent.

This is very similar to the normal base-b value in that you increment the rightmost column and if it overflows, set to zero and increment the next one. The only difference is that each column overflows with a different number.

So:



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

In this implementation, indexes[0]

it is used as the "rightmost" column. I was silent numberOfRRsInColumn()

, but it should be pretty obvious how to do this.

Then:

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


source






More articles:


All Articles