7

I am building an application that helps manage frisbee "hat tournaments". The idea is people sign up for this "hat tournament". When they sign up, the provide us with a numeric value between 1 and 6 which represents their skill level.

Currently, we are taking this huge list of people who signed up, and manually trying to create teams out of this based on the skill levels of each player. I figured, I could automate this by creating an algorithm that splits up the teams as evenly as possible.

The only data feeding into this is the array of "players" and a desired "number of teams". Generally speaking we are looking at 120 players and 8 teams.

My current thought process is to basically have a running "score" for each team. This running score is the total of all assigned players skill levels. I loop through each skill level. I go through rounds of picks once inside skill level loop. The order of the picks is recalculated each round based on the running score of a team.

This actually works fairly well, but its not perfect. For example, I had a range of 5 pts in my sample data array. I could very easily, manually swap players around and make the discrepancy no more then 1 pt between teams.. the problem is getting that done programatically.

Here is my code thus far: http://pastebin.com/LAi42Brq

Snippet of what data looks like:

[2] => Array
    (
        [user__id] => 181
        [user__first_name] => Stephen
        [user__skill_level] => 5
    )

[3] => Array
    (
        [user__id] => 182
        [user__first_name] => Phil
        [user__skill_level] => 6
    )

Can anyone think of a better, easier, more efficient way to do this? Many thanks in advance!!

hakre
  • 193,403
  • 52
  • 435
  • 836
Roeland
  • 3,698
  • 7
  • 46
  • 62
  • By "splitting them as evenly as possible", you mean having their individual total score mostly equal? For example, two teams of two players would be even if one had (2,6) and the other one (3,5)? – vgru Mar 15 '12 at 09:51
  • I refer you to the answers to http://stackoverflow.com/questions/9688392/picking-fair-teams-and-the-math-to-prove-it/9688717#comment12311258_9688717 – High Performance Mark Mar 15 '12 at 10:10

4 Answers4

6

I think you're making things too complicated. If you have T teams, sort your players according to their skill level. Choose the top T players to be captains of the teams. Then, starting with captain 1, each captain in turn chooses the player (s)he wants on the team. This will probably be the person at the top of the list of unchosen players.

This algorithm has worked in playgrounds (and, I dare say on the frisbee fields of California) for aeons and will produce results as 'fair' as any more complicated pseudo-statistical method.

High Performance Mark
  • 77,191
  • 7
  • 105
  • 161
  • This will probably work well in this scenario, since values are of the same order of magnitude. For a general partitioning problem, it would not necessarily give the optimal solution. – vgru Mar 15 '12 at 10:50
  • I'm sorry for the last guy that will be picked – Luca Martini Mar 15 '12 at 11:03
  • It seems, the data has to be suitable for this method. If I understand this correctly, players "6,5,5,3,3,1" would result in teams "6,5,3" (=14) and "5,3,1" (=9), right? – Leif Mar 15 '12 at 11:10
  • Yeah, there's always some weedy, ill-coordinated and asthmatic kid standing shivering in gym kit at the end. – High Performance Mark Mar 15 '12 at 11:10
  • @Leif: you are doing arithmetic on ordinal numbers. The whole point of my answer is that the skill levels are ordinal numbers, adding them up is not a valid operation. But you are right that the playground algorithm would produce teams, given your input data, in which each individual in team A is better than the corresponding member of team B. Just like in the playground. – High Performance Mark Mar 15 '12 at 11:13
  • @Leif a simple fix could be to make choose captain of team A, then twice captain B, then twice captain A, and so on (as we did in our playground, actually) – Luca Martini Mar 15 '12 at 11:24
2

A simple solution could be to first generating a team selection order, then each team would "select" one of the highest skilled player available. For the next round the order is reversed, the last team to select a player gets first pick and the first team gets the last pick. For each round you reverse the picking order.

First round picking order could be:

A - B - C - D - E

second round would then be:

E - D - C - B - A

and then

A - B - C - D - E etc.

h00ligan
  • 1,471
  • 9
  • 17
2

It looks like this problem really is NP-hard, being a variant of the Multiprocessor scheduling problem.

"h00ligan"s suggestions is equivalent to the LPT algorithm.

Another heuristic strategy would be a variation of this algorithm:

First round: pick the best, second round: pair the teams with the worst (add from the end), etc.

With the example "6,5,5,3,3,1" and 2 teams this would give the teams "6,1,5" (=12) and "5,3,3" (=11). The strategy of "h00ligan" would give the teams "6,3,3" (=12) and "5,5,1" (=11).

hmuelner
  • 8,093
  • 1
  • 28
  • 39
1

This problem is unfortunately NP-Hard. Have a look at bin packing which is probably a good place to start and includes an algorithm you can hopefully tweak, this may or may not be useful depending on how "fair" two teams with the same score need to be.

Jim
  • 22,354
  • 6
  • 52
  • 80
  • I believe the problem has a polynomial solution. The bin-packing problem is not a good reduction since: the values are in range `[1,6]`. I believe this problem can actually be solved polynomially using dynamic programming. However, the general case [scores are not limited to at most 6] is indeed NP-Hard, with a reduction from Subset Sum problem. – amit Mar 15 '12 at 11:03