An algorithm that creates “teams” based on the numeric value of a skill

Question

I am creating an application that helps manage Frisbee hat tournaments. The idea is that people sign up for this “hat tournament”. When they register, give us a numerical value between 1 and 6, which represents their skill level.

Currently, we take this huge list of people who signed up and manually try to create teams from this based on the skill levels of each player. I decided that I could automate this by creating an algorithm that breaks down the commands as evenly as possible.

The only data that goes into this is the array of “players” and the desired “number of teams”. Generally speaking, we look at 120 players and 8 teams.

My current thinking process is basically to have a “score” for each team. This account is the sum of all the skill levels of the designated players. I go through every skill level. I go through the selection rounds once inside the skill level cycle. The election order is selected in each round based on the assessment of the team.

It actually works pretty well, but its not perfect. For example, in my sample array, I had a range of 5 points. I could very easily manually change the players around and make a difference of no more than 1 pt between the teams .. the problem is that this is done programmatically.

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

Data display fragment:

[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 more efficient, more efficient way to do this? Thank you very much in advance!

Answer 1

I think you make it too complicated. If you have T teams, sort your players according to their skill level. Choose the best T players to be team captains. Then, starting with captain 1, each captain, in turn, chooses the players he wants in the team. This will probably be the person at the top of the list of unreleased players.

This algorithm worked on playgrounds (and, I believe, in the frieze fields of California) for eons and will yield results as “fair” as more complex pseudo-statistical methods.

Answer 2

A simple solution may be to first create a team of choice, then each team will "choose" one of the most qualified players. In the next round, the order is canceled, the last team to select a player receives the first choice, and the first team receives the last choice. For each round, you change the order of picking.

The order of the first round may be:

A - B - C - D - E

The second round will be as follows:

E - D - C - B - A

and then

A - B - C - D - E, etc.

Answer 3

It seems that this problem is really NP-hard, being an option Multiprocessing Planning Problem.

"The h00ligan sentences are equivalent to the LPT algorithm.

Another heuristic strategy would be a variation of this algorithm:

Round one: choose the best, second round: a pair of teams with the worst (add from the end), etc.

In the example “6,5,5,3,3,1” and 2 teams, this will give the commands “6,1,5” (= 12) and “5,3,3” (= 11), The strategy “h00ligan” will give commands "6.3.3" (= 12) and "5.5.1" (= 11).

Answer 4

This problem, unfortunately, is NP-Hard. Take a look at bin packing , which is probably a good place to run, and includes an algorithm that you can hope to tweak, it may or may not be useful depending on how “fair” two teams with the same score should be.