Results 1 to 4 of 4

Math Help - Teamizer

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    2

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Intermittentwow View Post
    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 \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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Intermittentwow View Post
    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 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).
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum