Hello ree1434-ga!
I had no idea how many people have written about this exact problem
until I did a simple search. There have been numerous papers written
about the ?Social Golfer? problem, some with incredible mathematical
detail. I did find a couple of sites that I believe answer this
question very well. Looking over your initial example, I notice that
each pairing is unique, but golfers may play *against* other golfers
more than once during the sequence. This is also how the problem is
addressed on the sites that I will reference.
- - - - - - - - - - - - - - - - - - - -
?SYMMETRY BREAKING AND THE SOCIAL GOLFER?
According to CiteSeer, Harvey Warwick?s article ?Symmetry Breaking and
the Social Golfer? is a frequently referenced article relating to
?highly symmetric problems in a constraint programming context?
(http://citeseer.ist.psu.edu/harvey01symmetry.html). Essentially, this
ordering of golfing partners represents a very ordered and symmetrical
problem. Developing an algorithm in order to determine the pairings
would be a boon since it could be adapted to other problems.
There is an article entitled ?Scheduling Golfers Locally? written by
Ivan Dotu1 and Pascal Van Hentenryck of Brown University that deals
with developing such an algorithm. You can read the entire PDF file at
http://www.cs.brown.edu/~pvh/social.pdf. Honestly, I found the whole
article very technical and confusing, but luckily elsewhere on their
site there is a very nice summary with an interactive grid to help
determine golf pairing, without all of the equations. The only
equation that is discussed is a simple one that determines the maximum
number of weeks that one could arrange pairs of golfers before there
is a repeated pair. See http://www.cs.brown.edu/people/sello/golf.html
for the full details.
The basic equation is defined as follows:
w = maximum number of weeks
g = number of groups/pairings
s = number of golfers
W <= [(g*s)-1]/(s-1)]
So in your example:
g = 6
s = 2
w <= [(6*2)-1/(2-1)
w <= [12-1]/(2-1)
w <= 11
So the maximum number of weeks possible, maintaining unique weekly
pairings, is 11. Of course, determining a shorter schedule would be
simpler, but not all golfers would play together.
Using the grid I mentioned above here is how an 11-week schedule would work out:
Week 1
1 2 vs. 3 4
5 6 vs. 7 8
9 10 vs. 11 12
Week 2
1 3 vs. 2 4
5 7 vs. 6 8
9 11 vs. 10 12
Week 3
1 4 vs. 2 3
5 8 vs. 6 7
9 12 vs. 10 11
Week 4
1 5 vs. 2 6
3 9 vs. 4 10
7 11 vs. 8 12
Week 5
1 6 vs. 2 5
3 10 vs. 4 9
7 12 vs. 8 11
Week 6
1 11 vs. 2 12
3 5 vs. 4 6
7 9 vs. 8 10
Week 7
1 12 vs. 2 11
3 6 vs. 4 5
7 10 vs. 8 9
Week 8
1 7 vs. 2 8
3 11 vs. 4 12
5 9 vs. 6 10
Week 9
1 8 vs. 2 7
3 12 vs. 4 11
5 10 vs. 6 9
Week 10
1 9 vs. 2 10
3 7 vs. 4 8
5 11 vs. 6 12
Week 11
1 10 vs. 2 9
3 8 vs. 4 7
5 12 vs. 6 11
Whew! There they all are. Thank goodness there is a grid that helps
work out such a complicated problem! I hope that this answers your
question. If you have need of any further clarification please let me
know how I can help. Thank you again! Oh, and welcome to Google
Answers!
Sincerely,
Boquinha-ga
Search strategy:
symmetry breaking and the social golfer |
