列表的可能组合

Question

我有一个对象的ArrayList，我想根据一组简单的规则创建所有可能的组合。存储在列表中的每个对象都包含一个squadNumber和一个字符串。以下是我正在存储的典型列表示例：

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

我想获取所有组合，其中每个squadNumber只能出现一次，例如：(1,A),(2,A),(3,C),(4,C)，然后下一个组合将是(1,A),(2,A),(3,C),(4,D)。我该如何在Java中处理呢？通常我会使用嵌套循环，但它们都被存储在一个列表中，这使得事情变得复杂。

谢谢， paintstripper

- paintstripper

---

使用Set，例如HashSet，而不是List。Sets保证唯一性。 - Bohemian

Answer 1

编辑过的内容

算法如下：

1. 按数字将所有小队分组。因此，我们有了1号小队的列表，另一个列表是2号小队，以此类推。
2. 运行深度优先搜索（dfs）。在第n步中，我们添加具有第n个数字的小队。

代码

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

- Mikita Belahlazau

---

它将是动态的，因此小组编号可以是任何内容。 - paintstripper