Возможные комбинации списка

Question

У меня есть массив объектов, для которых я хочу создать все возможные комбинации (согласно простому набору правил).Каждый объект, который хранится в списке, содержит 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?Обычно я бы использовал вложенный цикл, но тот факт, что все это хранится в одном списке, усложняет мне задачу.

Спасибо, painttstripper

Answer 1

EDITED

Алгоритм следующий:

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