Background:
I am writing a PHP, (mysql) script that helps us create the teams for our weekly golf match and have hit this interesting problem. While I have enough of a solution to write a brute force script (lots of nested for loops and case statements) the lazy side of me says the must be a more elegant mathematical solution to my problem. Any ideas welcome.
Problem:
We have a group of golfers(n) that we want to divide up into foursomes(teams of 4) by handicap a number 1 to 36 that represents their ability.
When the the number of golfers is a multiple of four, the problem is simple, order the list by their handicap and take the first n/4 golfers as A players the next as B, C and D players. Each team gets one player of each category randomly. (this is the easy part of the script)
It of course gets more interesting when the number of players is not an even multiple of four. In this case we create as many teams of 4 as we can leaving either 1, 2, or 3 teams of 3 depending on how many players we are short. These teams receive what is called a Blind Draw. At the end of the match If a team is missing a B player. They select a B Player at random from the other teams. Their four man score calculated using that B players score.
The question is how best to determine where the blind draw(s) should be located A,B,C, or D
Simplifying the problem a little lets just do two man teams, A's and B's. Take this list of players and handicaps;
Joe 6
Bob 7
Al 8
Steve 9
Mark 15
Dave 16
Jim 20
Visually it is pretty obvious the that the fairest assignment is to add a blind draw as a B player.
A players
Joe 6
Bob 7
Al 8
Steve 9
B Players
Mark 15
Dave 16
Jim 20
Blind Draw
As opposed to this;
A players
Joe 6
Bob 7
Al 8
Blind Draw
B Players
Steve 9
Mark 15
Dave 16
Jim 20
Mathematically:
If you take the possible ways of assigning the blind draw and then calculate the std deviation for each of the sub groups under each of the choices and sum them together you get relative merit of each of the Blind draw assignments. As shown below Choice 1 is the best grouping.
Shown here
Choice 1
Joe 6
Bob 7
Al 8
Steve 9
Std dev 1.29
Mark 15
Dave 16
Jim 17
Std dev 2.65
Sum of stddev 3.94
Choice 2
Joe 6
Bob 7
Al 8
Std dev 1.00
Steve 9
Mark 15
Dave 16
Jim 17
Std dev 4.55
Sum of stddev 5.55
So as expect Choice 1 is better lower stdev.
As you expand this problem to more groups and four man teams the programming of this gets pretty hairy. A lot of nested four loops.
Is there a more elegant solution??
Thanks in advance for any help