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