Các kết hợp có thể có trong danh sách

Question

Tôi có một danh sách các đối tượng mà tôi muốn tạo tất cả các kết hợp có thể (theo một bộ quy tắc đơn giản). Mỗi đối tượng được lưu trữ trong danh sách chứa một squadNumber và một chuỗi. Dưới đây là một ví dụ về một danh sách tiêu biểu tôi đang lưu trữ:

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

Tôi muốn có được tất cả các kết hợp trong đó mỗi squadNumber chỉ có thể xuất hiện một lần, ví dụ: (1, A), (2, A), (3, C), (4, C) thì sự kết hợp tiếp theo sẽ là (1, A), (2, A), (3, C), (4, D). Làm thế nào tôi sẽ đi về điều này trong java? Thông thường tôi sẽ sử dụng một vòng lặp lồng nhau, nhưng thực tế là tất cả được lưu trữ trong một danh sách làm phức tạp mọi thứ cho tôi.

Cảm ơn, paintstripper

Answer 1

EDITED

Thuật toán là như sau:

1. Chia tất cả các đội bằng số. Vì vậy, chúng tôi có danh sách các đội cho 1, danh sách khác cho các đội 2, v.v.
2. Chạy dfs. Ở bước thứ n, chúng ta thêm các đội với số thứ n.

Mã

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