Ok here we go... I have to do a round robin scheduling application for a non for profit group. I've been working at this for hours and have come up empty handed... so I went to the net for some help and here is what I found. I found this question and answer between these two guys and I basically want to put what they've said to code. I don't know if I'm really tired or what but I'm having trouble putting what they've said to code. If you could steer me on the right track it would be appreciated very much!!!!
Anyway without further adue here is the dialog between these two guys.... (sorry for the long post)
Round Robin Tournament Schedule
Date: 03/31/2000 at 14:43:25
From: Blake Kinley
Subject: Scheduling sports competitions
What is the principle or formula I need to do this without using
trial and error? I need to be able to create match schedules for up
to 32 teams.
Here is a sample for 6 Teams that I worked out using the
trial-and-error method.
Round 1:
Field A: Team 6 vs Team 1
Field B: Team 4 vs Team 3
Field C: Team 5 vs Team 2
Round 2: Round 3: Round 4: Round 5:
A: 1-3 A: 2-4 A: 3-5 A: 6-5
B: 6-2 B: 1-5 B: 6-4 B: 3-2
C: 5-4 C: 6-3 C: 2-1 C: 4-1
Notice That each team plays on each field a maximum of twice
(sometimes only once).
I need a method other than trial-and-error to create similar match
schedules for 8 Teams on 4 Fields, 10 Teams on 5 Fields, and so on up
to at least 32 Teams on 16 Fields.
HELP!
--------------------------------------------------------------------------------
Date: 04/03/2000 at 13:52:26
From: Doctor TWE
Subject: Re: Scheduling sports competitions
Hi Blake - thanks for writing to Dr. Math.
Scheduling a round-robin tournament is not as easy as it looks. There
is a systematic approach to scheduling that ensures that every team
plays every other team once with the minimum amount of "idle time" (or
byes). This method assumes that there are enough fields so that all
the games in a round can be played simultaneously. The technique is
sometimes referred to as the "polygon method." It has two variations,
depending on whether the total number of teams is an even number or an
odd number. I'll cover the odd case first.
POLYGON METHOD ROUND-ROBIN SCHDULING: ODD NUMBER OF TEAMS
---------------------------------------------------------
Let N = number of teams in the tournament. There will be N rounds
(since each team will play every other team once, and will have
exactly one idle round, or "bye"
. I will use five teams (A, B, C, D,
and E) in my example.
STEP 1: Draw a regular N-gon. (An N-gon is a polygon with N sides, for
example a triangle, pentagon, heptagon, etc.) Each vertex represents
one team, and can be labeled as such.
A
o
E o o B
o o
D C
STEP 2: Draw (N-1)/2 line segments connecting the vertices such that:
a) No vertex has more than one segment drawn to/from it, and
b) No segment is a rotation or reflection of another segment.
One easy method to ensure that these conditions are met is to "stripe"
the polygon. Draw the polygon such that the two lowest vertices are
horizontal. Connect these two with a horizontal segment. Connect the
two next lowest ones with another horizontal segment, etc. The top
vertex will remain unconnected. (This is because there is an odd
number of vertices.)
A
o
E o-------o B
o---o
D C
Each segment represents teams playing each other in the first round.
In my example, team E plays team B and team D plays team C. Team A is
idle in round one.
STEP 3: Rotate the polygon 1/Nth of a circle (i.e. one vertex point.)
You can either rotate the segments in the polygon (keeping the
vertices fixed) or you can rotate the vertices (keeping the segments
fixed). I'm going to rotate the vertices because it's easier to draw
with ASCII graphics. The new segments represent the match-ups for
round two.
E
o
D o-------o A
o---o
C B
In my example, team D plays team A and team C plays team B in round
two. Team E is idle.
STEP 4: Continue rotating the polygon until you return to your
original position. Each rotation represents the match-ups of the next
round. When you return to the original position, you don't record the
match-ups, as they were already played in round one. For example:
Round three: C-E, B-A (D idle)
D
o
C o-------o E
o---o
B A
Round four: B-D, A-E (C idle)
C
o
B o-------o D
o---o
A E
Round five: A-C, E-D (B idle)
B
o
A o-------o C
o---o
E D
One more rotation would bring me back to my original position. Thus,
my schedule looks like this:
Round Games: Idle
----- -------- ----
1 E-B, D-C A
2 D-A, C-B E
3 C-E, B-A D
4 B-D, A-E C
5 A-C, E-D B
Why does this work? Requiring (N-1)/2 segments in step 2 ensures that
there is only one idle team in each round, thus there will be the
minimum number of rounds required. The restriction that no vertex has
more than one segment drawn to/from it ensures that no team is
scheduled for more than one game in each round. And the restriction
that no segment is a rotation or reflection of another segment ensures
that no match-up will be repeated in a future round.
A final note: For N > 6, the "striping" method is not the only way of
drawing the segments for step 2, but it is the easiest. Here are two
ways of drawing them for a heptagon (N = 7):
A A
o o
G o-------o B G o / o B
X F o-----------o C F o/ \ o C
o-----o o o
E D E D
The "striping" method pairs G-B, F-C and E-D in round one, while the
alternate method pairs A-F, G-D and B-C in round one. Each of these
creates a valid schedule, they are not the same schedule with just
some of the rounds switched.
POLYGON METHOD ROUND-ROBIN SCHDULING: EVEN NUMBER OF TEAMS
---------------------------------------------------------
Let N = number of teams in the tournament. There will be N-1 rounds
(since each team will play every other team once, and there will be no
idle teams, or "byes". I will use six teams (A, B, C, D, E and F) in
my example.
STEP 1: Draw a regular (N-1)-gon. (for 4 teams draw a triangle, for 6
teams draw a pentagon, for 8 teams draw a heptagon, etc.) Place a
point in the center of the polygon. Each vertex and the center point
represent one team, and can be labeled as such.
A
o
E o o B
o F
o o
D C
STEP 2: Draw N/2 line segments connecting the vertices and the center
point such that:
a) No vertex (nor the center point) has more than one segment drawn
to/from it, and
b) No segment is a rotation or reflection of another segment.
This is essentially the same as the odd case, but the "idle" team
plays the "center" team.
"Striping" still works, but the top vertex must be connected to the
center point. For example
A
o
|
E o-------+-------o B
|
o F
o-------o
D C
Each segment represents teams playing each other in the first round.
In my example, team E plays team B, team D plays team C, and team A
plays team F in round one.
STEP 3: Rotate the polygon 1/Nth of a circle (i.e. one vertex point).
You can either rotate the segments in the polygon (keeping the
vertices fixed) or you can rotate the vertices (keeping the segments
fixed). I'm going to rotate the vertices because it's easier to draw
with ASCII graphics. The new segments represent the match-ups for
round two.
E
o
|
D o-------+-------o A
|
o F
o-------o
C B
In my example, team D plays team A, Team C plays team B, and team E
plays team F in round two.
STEP 4: Continue rotating the polygon until you return to your
original position. Each rotation represents the match-ups of the next
round. When you return to the original position, you don't record the
match-ups, as they were already played in round one. For example:
Round three: C-E, B-A, D-F
D
o
|
C o-------+-------o B
|
o F
o-------o
B A
Round four: B-D, A-E, C-F
C
o
|
B o-------+-------o D
|
o F
o-------o
A E
Round five: A-C, E-D, B-F
B
o
|
A o-------+-------o C
|
o F
o-------o
E D
One more rotation would bring me back to my original position. Thus,
my schedule looks like this:
Round Games:
----- -------------
1 E-B, D-C, A-F
2 D-A, C-B, E-F
3 C-E, B-A, D-F
4 B-D, A-E, C-F
5 A-C, E-D, B-F
You also mentioned restricting the number of fields in play. This can
be tricky. Usually, you can start the games for round one in timeslot
one, play the remaining round one games in timeslot two, and find
games from round two that don't involve teams already playing in
timeslot two, etc. If there are less than N/4 fields, the round one
games will fill timeslots one and two, and spill into timeslot three,
etc.
I hope this helps. If you have any more questions, write back.
- Doctor TWE, The Math Forum
Anyway without further adue here is the dialog between these two guys.... (sorry for the long post)
Round Robin Tournament Schedule
Date: 03/31/2000 at 14:43:25
From: Blake Kinley
Subject: Scheduling sports competitions
What is the principle or formula I need to do this without using
trial and error? I need to be able to create match schedules for up
to 32 teams.
Here is a sample for 6 Teams that I worked out using the
trial-and-error method.
Round 1:
Field A: Team 6 vs Team 1
Field B: Team 4 vs Team 3
Field C: Team 5 vs Team 2
Round 2: Round 3: Round 4: Round 5:
A: 1-3 A: 2-4 A: 3-5 A: 6-5
B: 6-2 B: 1-5 B: 6-4 B: 3-2
C: 5-4 C: 6-3 C: 2-1 C: 4-1
Notice That each team plays on each field a maximum of twice
(sometimes only once).
I need a method other than trial-and-error to create similar match
schedules for 8 Teams on 4 Fields, 10 Teams on 5 Fields, and so on up
to at least 32 Teams on 16 Fields.
HELP!
--------------------------------------------------------------------------------
Date: 04/03/2000 at 13:52:26
From: Doctor TWE
Subject: Re: Scheduling sports competitions
Hi Blake - thanks for writing to Dr. Math.
Scheduling a round-robin tournament is not as easy as it looks. There
is a systematic approach to scheduling that ensures that every team
plays every other team once with the minimum amount of "idle time" (or
byes). This method assumes that there are enough fields so that all
the games in a round can be played simultaneously. The technique is
sometimes referred to as the "polygon method." It has two variations,
depending on whether the total number of teams is an even number or an
odd number. I'll cover the odd case first.
POLYGON METHOD ROUND-ROBIN SCHDULING: ODD NUMBER OF TEAMS
---------------------------------------------------------
Let N = number of teams in the tournament. There will be N rounds
(since each team will play every other team once, and will have
exactly one idle round, or "bye"
. I will use five teams (A, B, C, D, and E) in my example.
STEP 1: Draw a regular N-gon. (An N-gon is a polygon with N sides, for
example a triangle, pentagon, heptagon, etc.) Each vertex represents
one team, and can be labeled as such.
A
o
E o o B
o o
D C
STEP 2: Draw (N-1)/2 line segments connecting the vertices such that:
a) No vertex has more than one segment drawn to/from it, and
b) No segment is a rotation or reflection of another segment.
One easy method to ensure that these conditions are met is to "stripe"
the polygon. Draw the polygon such that the two lowest vertices are
horizontal. Connect these two with a horizontal segment. Connect the
two next lowest ones with another horizontal segment, etc. The top
vertex will remain unconnected. (This is because there is an odd
number of vertices.)
A
o
E o-------o B
o---o
D C
Each segment represents teams playing each other in the first round.
In my example, team E plays team B and team D plays team C. Team A is
idle in round one.
STEP 3: Rotate the polygon 1/Nth of a circle (i.e. one vertex point.)
You can either rotate the segments in the polygon (keeping the
vertices fixed) or you can rotate the vertices (keeping the segments
fixed). I'm going to rotate the vertices because it's easier to draw
with ASCII graphics. The new segments represent the match-ups for
round two.
E
o
D o-------o A
o---o
C B
In my example, team D plays team A and team C plays team B in round
two. Team E is idle.
STEP 4: Continue rotating the polygon until you return to your
original position. Each rotation represents the match-ups of the next
round. When you return to the original position, you don't record the
match-ups, as they were already played in round one. For example:
Round three: C-E, B-A (D idle)
D
o
C o-------o E
o---o
B A
Round four: B-D, A-E (C idle)
C
o
B o-------o D
o---o
A E
Round five: A-C, E-D (B idle)
B
o
A o-------o C
o---o
E D
One more rotation would bring me back to my original position. Thus,
my schedule looks like this:
Round Games: Idle
----- -------- ----
1 E-B, D-C A
2 D-A, C-B E
3 C-E, B-A D
4 B-D, A-E C
5 A-C, E-D B
Why does this work? Requiring (N-1)/2 segments in step 2 ensures that
there is only one idle team in each round, thus there will be the
minimum number of rounds required. The restriction that no vertex has
more than one segment drawn to/from it ensures that no team is
scheduled for more than one game in each round. And the restriction
that no segment is a rotation or reflection of another segment ensures
that no match-up will be repeated in a future round.
A final note: For N > 6, the "striping" method is not the only way of
drawing the segments for step 2, but it is the easiest. Here are two
ways of drawing them for a heptagon (N = 7):
A A
o o
G o-------o B G o / o B
X F o-----------o C F o/ \ o C
o-----o o o
E D E D
The "striping" method pairs G-B, F-C and E-D in round one, while the
alternate method pairs A-F, G-D and B-C in round one. Each of these
creates a valid schedule, they are not the same schedule with just
some of the rounds switched.
POLYGON METHOD ROUND-ROBIN SCHDULING: EVEN NUMBER OF TEAMS
---------------------------------------------------------
Let N = number of teams in the tournament. There will be N-1 rounds
(since each team will play every other team once, and there will be no
idle teams, or "byes"
. I will use six teams (A, B, C, D, E and F) in my example.
STEP 1: Draw a regular (N-1)-gon. (for 4 teams draw a triangle, for 6
teams draw a pentagon, for 8 teams draw a heptagon, etc.) Place a
point in the center of the polygon. Each vertex and the center point
represent one team, and can be labeled as such.
A
o
E o o B
o F
o o
D C
STEP 2: Draw N/2 line segments connecting the vertices and the center
point such that:
a) No vertex (nor the center point) has more than one segment drawn
to/from it, and
b) No segment is a rotation or reflection of another segment.
This is essentially the same as the odd case, but the "idle" team
plays the "center" team.
"Striping" still works, but the top vertex must be connected to the
center point. For example
A
o
|
E o-------+-------o B
|
o F
o-------o
D C
Each segment represents teams playing each other in the first round.
In my example, team E plays team B, team D plays team C, and team A
plays team F in round one.
STEP 3: Rotate the polygon 1/Nth of a circle (i.e. one vertex point).
You can either rotate the segments in the polygon (keeping the
vertices fixed) or you can rotate the vertices (keeping the segments
fixed). I'm going to rotate the vertices because it's easier to draw
with ASCII graphics. The new segments represent the match-ups for
round two.
E
o
|
D o-------+-------o A
|
o F
o-------o
C B
In my example, team D plays team A, Team C plays team B, and team E
plays team F in round two.
STEP 4: Continue rotating the polygon until you return to your
original position. Each rotation represents the match-ups of the next
round. When you return to the original position, you don't record the
match-ups, as they were already played in round one. For example:
Round three: C-E, B-A, D-F
D
o
|
C o-------+-------o B
|
o F
o-------o
B A
Round four: B-D, A-E, C-F
C
o
|
B o-------+-------o D
|
o F
o-------o
A E
Round five: A-C, E-D, B-F
B
o
|
A o-------+-------o C
|
o F
o-------o
E D
One more rotation would bring me back to my original position. Thus,
my schedule looks like this:
Round Games:
----- -------------
1 E-B, D-C, A-F
2 D-A, C-B, E-F
3 C-E, B-A, D-F
4 B-D, A-E, C-F
5 A-C, E-D, B-F
You also mentioned restricting the number of fields in play. This can
be tricky. Usually, you can start the games for round one in timeslot
one, play the remaining round one games in timeslot two, and find
games from round two that don't involve teams already playing in
timeslot two, etc. If there are less than N/4 fields, the round one
games will fill timeslots one and two, and spill into timeslot three,
etc.
I hope this helps. If you have any more questions, write back.
- Doctor TWE, The Math Forum
