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:
\begin{pmatrix} &P_{1} &P_{4} &P_{7} \\ &P_{2} &P_{5} &P_{8} \\ &P_{3} &P_{6} &P_{9} \end{pmatrix}

The first step was to determine the combinations. Information on the combination formulae can be found here: http://en.wikipedia.org/wiki/Combination. 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 was 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 be able to 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)
        unique_teams.add(frozenset({t1, t2, t3}))

    return unique_teams

The code above is designed for the 3 team case. It would need to be modified to deal with other amounts of teams.

In working this problem out I have developed the formula to calculate the combinations for any number of teams and any player pool size:

This is the general equation in latex for the number of combinations:
C = \frac{\prod_{x=0}^{T-1}\frac{(P-xP_{T})!}{P_{T}!(P-(x+1)P_{T})!}}{T!} \\ \\ \text{Where:}\\ T = \text{Number of Teams}\\ P_{T} = \text{Number of Players Per Team}\\ P = \text{Player Pool}\\ C = \text{Number of Combinations}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s