java - Combinaciones de Map<Object, List<Object>>

hashmap combinations

Question

Tengo un HashMap<GC, List<RR>> con datos de muestra como:

key   values

gc1 - rr1
    - rr2
    - rr3

gc2 - rr4
    - rr5

gc3 - rr6

Y necesito crear todas las combinaciones posibles de RR de diferentes GC como:

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

Lo que he intentado hasta ahora es, como sugiere @Sanket Makani, convertir mi HashMap<GC, List<RR>> en una List<List<RR>> , y luego recorrer todos los elementos como:

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

Esto no funciona para mí, ya que agrupa todo el RR dentro de un GC como:

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

Entonces mi pregunta es, ¿cómo puedo adaptar mi código para obtener el resultado esperado?

PD: estoy trabajando con Java6 por desgracia, por lo que no se permiten lambdas / streams.

PS2: he visto preguntas similares, pero no puedo encontrar un ejemplo exacto de lo que estoy buscando.

EDITAR:

Esta es mi implementación final con la respuesta de @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);

}

Answer 1

Aquí hay una solución recursiva:

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

Answer 2

Todo lo que realmente necesita hacer es trabajar a través de una lista de índice creciente:

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

Debería ser obvio cómo traducir cada una de esas filas en valores de su estructura de datos. por ejemplo, 0,0,0 mapas para rr1, rr4, rr6 . Esto implicará convertir el mapa en una lista para que los índices sean consistentes.

Es muy parecido a un recuento de base-b normal donde se incrementa la columna más a la derecha y si se desborda, se pone a cero e incrementa la siguiente. La única diferencia es que cada columna se desborda en un número diferente.

Asi que:

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

Esta implementación usa indexes[0] como la columna "más a la derecha". He pasado por alto numberOfRRsInColumn() , pero debería ser bastante obvio cómo hacerlo.

Entonces:

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