1. ## Teamizer

Hello I'm new to these forums. A problem has been driving me mad for weeks. I'm hoping someone can guide me in the right path.

Here's the problem:

There are 8 people, 4 on each team (4 vs 4). Each persons skill level is rated between 5-40 (5 being a complete noob). The goal is to create the fairest teams possible (the lowest possible difference in skill between team 1 and 2).

Do I need advanced University math knowledge to solve this problem? Any guidance would be appreciated.

Here's a sample player list

John: 10
Mark: 15
Mike: 34
Matt: 23
Bob: 18
Tyler: 13
Conor: 29
Rafa: 25

2. Originally Posted by Intermittentwow
Hello I'm new to these forums. A problem has been driving me mad for weeks. I'm hoping someone can guide me in the right path.

Here's the problem:

There are 8 people, 4 on each team (4 vs 4). Each persons skill level is rated between 5-40 (5 being a complete noob). The goal is to create the fairest teams possible (the lowest possible difference in skill between team 1 and 2).

Do I need advanced University math knowledge to solve this problem? Any guidance would be appreciated.

Here's a sample player list

John: 10
Mark: 15
Mike: 34
Matt: 23
Bob: 18
Tyler: 13
Conor: 29
Rafa: 25
Is a team's skill level just the sum of the skill levels of its team members? I'll assume yes.

For 2 teams of 4, I would just write a brute force computer program that exhaustively tries every combination. There will be be $\displaystyle \left(\frac{1}{2}\right)\binom{8}{4}=35$ possible ways to split up into teams.

What you would do is take the sum of all player's scores, call it a name like team2 (you'll see why in a bit), then pick out players one by one (using, for example, four nested for() loops, or you could use recursion), and each time you pick a player, you add that player's skill to a variable like team1, and you subtract that player's skill from team2, so by the end, you'll take abs(team1 - team2) where abs() gives absolute value, and keep track of a minimum.

If you want to go the (to me) long way, and just list them all out, you can work systematically as follows.

{1,2,3,4,5,6,7,8}

{1,2,3,4}
{1,2,3,5}
...
{1,2,3,8}
{1,2,4,5}
{1,2,4,6}
...
{1,3,4,5}
...
{5,6,7,8}

Listing out all of these will result in 70 4-subsets (which is 8 choose 4), which will be double of what you want because {1,2,3,4} is equivalent to {5,6,7,8}, etc. Hopefully you follow what I wrote, or got the gist.

3. Thanks for the reply. I know exactly what you're saying. But brute force isn't very mathematical. I was under the expression that such a problem could be expressed as a mathematical equation.

4. Originally Posted by Intermittentwow
Thanks for the reply. I know exactly what you're saying. But brute force isn't very mathematical. I was under the expression that such a problem could be expressed as a mathematical equation.
Maybe there exists such an equation. But this problem sounds a bit like the example on this page, for which there is no "fast" algorithm known (where "fast" is in terms of the time complexity of the algorithm, such as $\displaystyle O(n^2)$ etc.). But this may be an easier problem. For larger size teams I would have to think and maybe could point you in the direction of an algorithm faster than brute force. Nevertheless, brute force won't take more than a few milliseconds for n=8, if that. And to make it a bit faster you can add backtracking (where you terminate paths when they exceed the current minimum).