2016-03-12

# Team Combinations from a Limited Pool of Players

I had to determine an arrangement of teams from a player pool. Specifically there were 9 players that needed to be organized into fair teams. It seemed straight forward to arrange them into 3 teams of 3 players. The other caveat was that the teams needed to be as fair as possible. Some players were highly skilled while others were not. It wouldn’t be fair to stack the best players on a single team. In order to determine a fair team I had to figure out how many combinations of teams were possible. This would allow me to iterate through all of the combinations and apply a metric to each combination. The combination that produced the minimal value would be the optimal arrangement.

Here is what the player pool looks like:

=======
1  4  7
2  5  8
3  6  9
=======

The first step was to determine the combinations. Information on the combination formula can be found here. It is straight forward to apply it to simple sequences. For example, to determine the number of combinations of one team of 3 players out of a pool of nine players is as follows. Basically, since there are only 3 slots on a team and we cannot have duplicate players, that is, once a player is selected, the pool of available players shrinks.

The following calculation illustrates the number of combinations a 3 person team can have from a pool of 9 players:

$T_{1} = \frac{9\times 8\times 7}{3!} = 84$

Since the number of combinations that the first team can have is 84, how many combinations are there for the second team. That can be calculated as follows:

$T_{2} = \frac{6\times 5\times 4}{3!} = 20$

The number of combinations for the second team is 20. To calculate, the combinations for the second team, we have to realize that there are only 6 players left in the pool to choose from. Hence only 20 ways to make the second team. After the first team and second team are constructed, there are only 3 players left in the pool. Our third team is decided for us, how convenient! There is only one way to express the third team.

These calculations do not indicate how many ways there are to construct the 3 teams, they only gives us an idea of the ways to construct the individual teams. In order to determine the number of combinations of teams we need to multiply the individual combinations together.

$84\times 20\times 1 = 1680$

The results look a little high and that is because what we calculated the permutations of the teams and not the combinations. To fix that we divide the permutations by the number of ways that the teams can be arranged (the reason we don’t want permutations is because team 1, team 2, team 3 is the same as team 2, team 1, team 3). To fix this, divide the team permutations by the number of ways to arrange the teams, 3!

$\frac{84\times 20\times 1}{3!} = 280$

Now that we know how many combinations, we can write a program to generate the combinations and evaluate them.

players_per_team = 3

player_pool = {'p1', 'p2', 'p3', 'p4', 'p5', 'p6', 'p7', 'p8', 'p9' }

unique_teams = set()

for team1 in generate_valid_team_combinations(players_per_team, player_pool):
t1 = frozenset(team1)
reduced_pool = player_pool.difference(t1)

for team2 in generate_valid_team_combinations(players_per_team, reduced_pool):
t2 = frozenset(team2)
reduced_pool2 = reduced_pool.difference(t2)
t3 = frozenset(reduced_pool2)
$C = \frac{\prod_{x=0}^{T-1} \cdot \frac{(P-xP{T})!}{P{T}!(P-(x+1)P{T})!}}{T!}$