Round Robin support?

It looks like a RR would fit into the framework - I'll put it on the list.

I would like that, too!

from: http://www.devenezia.com/downloads/round-robin/sci.math.num-analysis.rou...

Here is a formal statement of the problem: There are n teams which must be
scheduled in n * (n-1) / 2 games in some number of rounds. Multiple games can be
played simultaneously during a single round. We wish to minimize the number of
rounds, subject to the following 3 conditions: (1) every team must play every
other team; (2) each team can be involved in at most one game per round; and (3)
If during a round team i plays team j, then in that same round team j plays team
i.

A schedule only makes sense for n >= 2; however, the algorithm works for n=1 as
well. Notice that if n is even, then n-1 rounds are required; if n is odd, then n
rounds are required and each team is idle in exactly one round.

Here is the algorithm and its proof of correctness. I will number the teams from 0
to (n-1), and number the rounds beginning at 0.

-----------------------

Suppose n is odd. Make an n-by-n array called S, where S(r, i) = j iff team i
plays team j in round r. If S(r, i) = i, this means that team i is idle in round
r. Define S as
S(r, i) = (n + r - i - 1) mod n
Below is the array in the case where n = 5.
4 3 2 1 0
0 4 3 2 1
1 0 4 3 2
2 1 0 4 3
3 2 1 0 4

I will now show that this definition of S satisfies the three properties.

(1) Every team must play every other team.

The ith column of the array lists the teams which team i plays. By construction,
all of the numbers from 0 to (n-1) inclusive appear in each column. Thus, every
team plays every other team.

(2) Each team can be involved in at most one game per round.

The rth row of the array lists the teams which play in round r. By construction,
all of the numbers from 0 to (n-1) inclusive appear in each row exactly once.
Thus, each team is involved in exactly one game per round. (Recall that if the
array lists that a team plays itself, then it is actually idle during that round.)

(3) If during a round team i plays team j, then during that same round team j
plays team i.

Suppose that i >= r. Then S(r, i) = (n + r - i - 1) mod n = n + r - i - 1 = j.
Then S(r, j) = (n + r - [n + r - i - 1] - 1) mod n = i mod n = i.

Now suppose that i < r. Then S(r, i) = (n + r - i - 1) mod n = r - i - 1 = j. Then
S(r, j) = (n + r - [r - i - 1] - 1) mod n = (n + i) mod n = i.

Thus, if during a round team i plays team j, then during that same round team j
plays team i.

Therefore, the algorithm is correct for odd n.

-----------------------

Now suppose that n is even and n >= 2. Make an (n-1)-by-n array called S, where
S(r, i) = j iff team i plays team j in round r. Notice that S has (n-1) rows and n
columns.

Let S' the schedule for (n-1) teams. Notice that S' is (n-1)-by-(n-1). Set the
first (n-1) rows of S to be identical to S', and let the last column of S be all
(n-1)'s. For example, when n = 6, S looks like
4 3 2 1 0 5
0 4 3 2 1 5
1 0 4 3 2 5
2 1 0 4 3 5
3 2 1 0 4 5
Now, for i = 0 to (n-2) inclusive, let r = (2i + 1) mod (n-1), and swap the
numbers at S(r, i) and S(r, n-1). When n = 6, the array becomes
4 3 5 1 0 2
5 4 3 2 1 0
1 0 4 5 2 3
2 5 0 4 3 1
3 2 1 0 5 4
This is the schedule for n teams. S can be written as a formula:
S(r, i) = { n-1, if r = (2i + 1) mod (n-1) and i <
(n-1)
{ p, if i = n-1; where p is defined
such that r = (2p+1) mod (n-1)
{ ( (n-1) + r - i - 1) mod (n-1), otherwise

I will now show this definition of S satisfies the three properties.

(1) Every team must play every other team.

Note that S' satisfies property (1). Thus, each column of S' contains the numbers
from 0 to (n-2) inclusive. Thus, in the original S, every team from 0 to (n-2)
plays every other team in this range, including itself. After the swapping, the
entry i in row i is changed to a (n-1). Thus, every team in the range 0 to (n-2)
inclusive plays every other team, and is never idle.

This swapping swaps the numbers from 0 to (n-2) inclusive into column (n-1). Thus,
team (n-1) plays all of the other teams, and is never idle.

Thus, every team plays every other team.

(2) Each team can be involved in at most one game per round.

Note that S' satisfies property (2). Thus, each row of S' contains the numbers
from 0 to (n-2) inclusive. The last column of the original S is all (n-1)'s. Thus,
each row of the original S contains the numbers from 0 to (n-2) inclusive.

(3) If during a round team i plays team j, then during that same round team j
plays team i.

Note that S' satisfies property (3). Thus, we only need to check on the occasions
where a swap occurred.

Suppose r = (2i + 1) mod (n-1) and i < (n-1). Then S(r, i) = n-1 = j. Then S(r, j)
= p where r = (2p+1) mod (n-1). However, notice that p = i satisfies r = (2p+1)
mod (n-1). Thus, S(r, j) = i.

Suppose i = n-1. Then S(r, i) = p = j where r = (2p+1) mod (n-1). Notice j <
(n-1). There are two cases. Either r = (2j+1) mod (n-1), or it doesn't. Let's take
the first case, so r = (2j+1) mod (n-1). Then S(r, j) = n-1, as desired. Let's
take the second case, so it is not true that r = (2j+1) mod (n-1). However, j = p,
and p is defined such that r = (2p+1) mod (n-1). Thus r != r, a contradiction, so
this case is impossible.

Therefore, the algorithm is correct for even n.

-----------------------

Generating the array S can be done in quadratic time.

-----------------------------------------------
Adam Florence
Cornell University
PhD student in Computer Science

+1 would love this option too.

Any update on this? I am interested in helping with development.

following

janis please use the Follow button at the top right instead of adding comments.

Matt, sorry, my bad.

thanks for the info :)

Round Robin is a sub module of Tournament: http://drupal.org/project/tournament