Combinazioni possibili di un elenco

Question

Ho un array di oggetti che voglio creare tutte le combinazioni possibili (secondo un semplice insieme di regole). Ogni oggetto che è memorizzato nella lista contiene un numero di squadra e una stringa. Ecco un esempio di un tipico elenco sto Memorizzazione:

0: 1, A 
1: 1, B 
2: 2, A 
3: 2, B 
4: 3, C 
5: 3, D 
6: 4, C 
7: 4, D 

voglio ottenere tutte le combinazioni in cui ogni squadNumber può essere presente una sola volta, ad esempio: (1, A), (2, A), (3, C), (4, C) quindi la combinazione successiva sarebbe (1, A), (2, A), (3, C), (4, D). Come andrei su questo in Java? Di solito userei un ciclo annidato, ma il fatto che tutto sia memorizzato in una lista complica le cose per me.

Grazie, sverniciatore

Answer 1

CURATE

algoritmo è il seguente:

1. Split tutte le squadre da numeri. Quindi abbiamo una lista con le squadre per 1, un'altra lista per squadre 2, ecc.
2. Esegui dfs. All'ennesimo passo aggiungiamo squadre con l'ennesimo numero.

Codice

// Split squads by numbers, so we can iterate through each number independently. 
private Map<Integer, List<Squad>> splitSquadsByNumbers(List<Squad> squads) { 
    Map<Integer, List<Squad>> res = new HashMap<Integer, List<Squad>>(); 
    for (Squad squad : squads) { 
     if (res.get(squad.getNumber()) == null) { 
      res.put(squad.getNumber(), new ArrayList<Squad>()); 
     } 
     res.get(squad.getNumber()).add(squad); 
    } 
    return res; 
} 

List<Integer> squadNumbers; 
Map<Integer, List<Squad>> squadsByNumbers; 
Stack<Squad> stack; 

// Iterating through each squad with number squadNumbers[position] and try to add to stack, at the end pop it from stack. 

private void dfs(int position) { 
    if (position == squadNumber.size()) { 
     System.out.println(stack.toString()); 
    } else { 
     for (Squad squad : squadsByNumbers.get(squadNumber.get(position))) { 
      stack.push(squad); 
      dfs(position + 1); 
      stack.pop(); 
     } 
    } 
} 

private void main(List<Squad> squads) { 
    squadsByNumbers = splitSquadsByNumbers(squads); 
    squadNumber = new ArrayList(squadsByNumber.keySet()); 
    Collections.sort(squadNumbers); 
    stack = new Stack<Squad>(); 
    dfs(0); 
}