Scheduling algorithm for a round-robin tournament?
I recently did studying stuff and meet up with Donald Knuth. But i didn't found the right algorithm to my problem.
The Problem We have a league with n players. every week they have a match with one other. in n-1 weeks every team fought against each other. there are n/2 matches a day. but one team can only fight once in a week. if we generate an (n/k) combination we get all of the combinations... (assuming k = 2) but i need to bring them in the right order.
My first suggestion was... not the best one. i just made an array, and then let the computer try if he finds the right way. if not, go back to the start, shuffle the array and do it again, well, i programmed it in PHP (n=8) and what comes out works, but take many time, and for n=16 it gives me a timeout as well.
So i thought if maybe we find an algorithm, or anybody knows a book which covers this problem.
And here's my code: http://pastebin.com/Rfm4TquY
Answer
The classic algorithm works like this:
Number the teams 1..n. (Here I'll take n=8.)
Write all the teams in two rows.
1 2 3 4
8 7 6 5
The columns show which teams will play in that round (1 vs 8, 2 vs 7, ...).
Now, keep 1 fixed, but rotate all the other teams. In week 2, you get
1 8 2 3
7 6 5 4
and in week 3, you get
1 7 8 2
6 5 4 3
This continues through week n-1, in this case,
1 3 4 5
2 8 7 6
If n is odd, do the same thing but add a dummy team. Whoever is matched against the dummy team gets a bye that week.