CODEWITHSUNDEEP
javalistcombinations
paintstripper
paintstripper

Reputation: 97

Possible combinations of a list

I have an arraylist of objects that I want to create all possible combinations (according to a simple set of rules). Each object that is stored in the list holds a squadNumber and a string. Here is an example of a typical list I am storing:

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

I want to get all the combinations where each squadNumber can only be present once, for example: (1,A),(2,A),(3,C),(4,C) then the next combination would be (1,A),(2,A),(3,C),(4,D). How would I go about this in java? Usually I would use a nested loop, but the fact that it's all being stored in one list complicates things for me.

Thanks, paintstripper

Upvotes: 5

Views: 854

Answers (1)

Mikita Belahlazau
Mikita Belahlazau

Reputation: 15434

EDITED

Algorithm is following:

  1. Split all squads by numbers. So we have list with squads for 1, another list for squads 2, etc.
  2. Run dfs. At nth step we add squads with nth number.

Code

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

Upvotes: 3

Related Questions