Seeded tournament round robin algorithm
Borrall Wonnell
but I'm stuck so I though I'd appeal for some help.
The goal is to create an efficient order of play that is proper given
the seeding. Honestly, I have no idea what 'proper' means in this
context, except to say that the top player should have the easiest
path through the round robin (starting with the easiest matches,
finishing with the hardest). The next seed would have the next
easiest path, and so on.
For example, in a 4-player RR (players {A,B,C,D} ranked in order)
there should be 3 rounds of play:
Round 1: A-D B-C
Round 2: A-C B-D
Round 3: A-B C-D
Is this something that can be generalized to any number of even
players? Since an odd number of players results in a Bye every round,
is there a way to generalize to that case?
Any thoughts or pointers would be appreciated. Like I said, it seems
like there should already be a solution for this, I just couldn't find
it on the interwebs.
Ray Koopman
Borrall Wonnell
> http://groups.google.com/group/sci.math.num-analysis/msg/e1ea67d609d9...
Thanks, but I should have stated that I already spent a few hours
looking for information relating to the subject. The method you link
to is not based on priority/seeding...it merely ensures that all
players play all other players. While this method does guarantee
efficiency, it disregards order of play.
Using that method, changing the order of players (e.g. 1,2,3,4,5,6 vs.
1,2,3,6,5,4) results in a different solution. Changing which player
is 'fixed' also affects the solution. The number of solutions
increases with the # of players (n)...I'm looking for the optimal
solution to meet the criteria for 'proper' order.
Using the linked method, I re-ordered the rounds such that the #1
player plays against progressively stronger players (i.e. criteria is
met for player #1. This is great for the first player but disregards
the other players. It also disregards the case where a Bye is present
in each round (n is odd).
I suppose I could do a brute-force approach that evaluates all
possible solutions and then choose the best fit. It just seems that
there should be a more elegant approach.
Dann Corbit
@o7g2000prn.googlegroups.com>, dbon...@gmail.com says...
>
> On Feb 15, 4:19 am, Ray Koopman <koop...@sfu.ca> wrote:
> > On Feb 14, 6:17 pm, Borrall Wonnell <dbonn...@gmail.com> wrote:
>
> > > Any thoughts or pointers would be appreciated. Like I said, it seems
> > > like there should already be a solution for this, I just couldn't find
> > > it on the interwebs.
> >
> > http://groups.google.com/group/sci.math.num-analysis/msg/e1ea67d609d9...
>
> Thanks, but I should have stated that I already spent a few hours
> looking for information relating to the subject. The method you link
> to is not based on priority/seeding...it merely ensures that all
> players play all other players. While this method does guarantee
> efficiency, it disregards order of play.
That is the definition of a round robin tournament. I suspect you want
a swiss tournament, where the seeding matters (seeding is irrelevent in
round-robin format).
See:
http://en.wikipedia.org/wiki/Swiss-system_tournament
> Using that method, changing the order of players (e.g. 1,2,3,4,5,6 vs.
> 1,2,3,6,5,4) results in a different solution. Changing which player
> is 'fixed' also affects the solution. The number of solutions
> increases with the # of players (n)...I'm looking for the optimal
> solution to meet the criteria for 'proper' order.
>
> Using the linked method, I re-ordered the rounds such that the #1
> player plays against progressively stronger players (i.e. criteria is
> met for player #1. This is great for the first player but disregards
> the other players. It also disregards the case where a Bye is present
> in each round (n is odd).
>
> I suppose I could do a brute-force approach that evaluates all
> possible solutions and then choose the best fit. It just seems that
> there should be a more elegant approach.
Here you will find some sample programs for tournament scheduling:
http://cap.connx.com/tournament_software/
Borrall Wonnell
> > > Any thoughts or pointers would be appreciated. Like I said, it seems
> > > like there should already be a solution for this, I just couldn't find
> > > it on the interwebs.
>
> >http://groups.google.com/group/sci.math.num-analysis/msg/e1ea67d609d9...
>
> Thanks, but I should have stated that I already spent a few hours
> looking for information relating to the subject. The method you link
> to is not based on priority/seeding...it merely ensures that all
> players play all other players. While this method does guarantee
> efficiency, it disregards order of play.
>
> possible solutions and then choose the best fit. It just seems that
> there should be a more elegant approach.
This is pretty close to the result I want, I'm just interested in how
to generate it:
http://www.wtta.co.nz/pdf/resourse_pdf/round_robins.pdf
Borrall Wonnell
> That is the definition of a round robin tournament. I suspect you want
> a swiss tournament, where the seeding matters (seeding is irrelevent in
> round-robin format).
>
> See:http://en.wikipedia.org/wiki/Swiss-system_tournament
>
The Swiss system is an option I plan on using where necessary, but it
doesn't make sense for a small number of players (in my case, n <=
8). I still want to use a round robin format in those situations.
You are correct: mathematically speaking, a round robin does not
depend on seeding. In practice this is not the case; order of play
matters when dealing with real people instead of numbers. As stated,
I'm looking to provide the 'easiest' match order for the #1 player,
followed by the 2nd easiest match order for the #2 player and so on.
That doesn't change the fact that it's a round-robin...it's merely a
subset of all possible solutions for a n-player round robin.
I guess the answer isn't as simple as I had hoped. Maybe I'll use a
table lookup after all :\
>
> Here you will find some sample programs for tournament scheduling:http://cap.connx.com/tournament_software/
Thanks, I'll have a look to see if anything points me in the right
direction.
Ray Koopman
> This is pretty close to the result I want, I'm just interested in how
> to generate it:http://www.wtta.co.nz/pdf/resourse_pdf/round_robins.pdf
Here is some Mathematica code that implements the algorithm that
Ron Shepard gave. It fixes 1 and rotates 2...n. I think it does
a better job of recognizing the seeding than the pdf you found.
Use this when n is even:
n = 8; x = Range@n; Table[{r,Sequence@@Sort@
First@{Table[Sort@{x[[i]],x[[n+1-i]]},{i,n/2}],
x = Join[{1},RotateRight@Rest@x]}},{r,n-1}]
{1, {1, 8}, {2, 7}, {3, 6}, {4, 5}}
{2, {1, 7}, {2, 5}, {3, 4}, {6, 8}}
{3, {1, 6}, {2, 3}, {4, 8}, {5, 7}}
{4, {1, 5}, {2, 8}, {3, 7}, {4, 6}}
{5, {1, 4}, {2, 6}, {3, 5}, {7, 8}}
{6, {1, 3}, {2, 4}, {5, 8}, {6, 7}}
{7, {1, 2}, {3, 8}, {4, 7}, {5, 6}}
Use this when n is odd:
n = 7; x = Range[n+1]; Table[{r,Sequence@@Sort@
First@{Table[Sort@{x[[i]],x[[n+2-i]]},{i,(n+1)/2}],
x = Join[{1},RotateRight@Rest@x]}},{r,n}]/.n+1->"-"
{1, {1, -}, {2, 7}, {3, 6}, {4, 5}}
{2, {1, 7}, {2, 5}, {3, 4}, {6, -}}
{3, {1, 6}, {2, 3}, {4, -}, {5, 7}}
{4, {1, 5}, {2, -}, {3, 7}, {4, 6}}
{5, {1, 4}, {2, 6}, {3, 5}, {7, -}}
{6, {1, 3}, {2, 4}, {5, -}, {6, 7}}
{7, {1, 2}, {3, -}, {4, 7}, {5, 6}}
Jos van Kan
To determine the round in which player k plays player l take the bitwise
equivalence between the base 2 representation of k and l. (that is a 1 for equal
bits and a 0 for different bits) Rounds numbered from 0 to 2^p-2.
Example: with 16 players players numbered from 0000_2 to 1111_2. Top player is
0000_2, bottom player is 1111_2. Note that top players (first bit 0) meet bottom
players (first bit 1) in early rounds (first bit 0). You can apply this argument
recursively to show that within subgroups the matches against peers come latest.
Top player meets his adversaries in reverse order, bottom player meets his
adversaries in natural order.
Player 12 (1100) meets player 7 (0111) in round 4 (0100), etc.
Jos