From: Adam Florence [aflorenc@cam.cornell.edu]
Sent: Wednesday, February 16, 2000 1:19 PM
To: DCorbit@SolutionsIQ.com
Cc: aflorenc@marshall.cam.cornell.edu
Subject: Re: Your round robin tournament program

The code was written by me. You can use it as long as you state that
I was the author, and give my e-mail address, "aflorenc@acm.org" .

Enjoy,

Adam Florence


> ------_=_NextPart_000_01BF78BA.EEC5A566
> Content-Type: text/plain;
> 	charset="iso-8859-1"
> 
> The attached program appears to have been written by you.  I would like to
> know the copyright status, and if it can be used in an open source
> initiative for chess tournament management.
> 
> 
> ------_=_NextPart_000_01BF78BA.EEC5A566
> Content-Type: application/octet-stream;
> 	name="roundrobin.c"
> Content-Transfer-Encoding: quoted-printable
> Content-Disposition: attachment;
> 	filename="roundrobin.c"
> 
> /*
>    Re: RoundRobin tournament problem solvable? by Adam Florence
>    reply to this message
>    post a message on a new topic
>    Back to messages on this topic
>    Back to sci.math.num-analysis
>    << previous | next >>
> 
>    =
> ------------------------------------------------------------------------=
> --------
> 
>    Subject:      Re: RoundRobin tournament problem solvable?
>    Author:       Adam Florence <aflorenc@cs.cornell.edu>
>    Organization: Cornell Univ. CS Dept, Ithaca NY 14853
>    Date:         Fri, 31 Oct 1997 16:42:17 -0500
> 
>    Michael O'Donnell wrote:
> 
>    > Once upon a time I devised a simple (if devious) and apparently
>    > bulletproof (hah!) algorithm for generating RoundRobin tournament
>    > schedules (arranging an arbitrary number of contestants in pairs,
>    > pitting each against the other exactly once in a series of rounds
>    > with nobody ever sitting idle) but now I've heard that this
>    > problem is supposed to be either very hard or even unsolvable (NP
>    > complete?).  Since I can't believe that a math-ninny like me has
>    > achieved anything notable in this discipline I'm looking for
>    > confirmation that this problem is indeed just another simple,
>    > oft-solved puzzle, and not actually difficult for anyone but me...
>    >
>    > As seeming confirmation of its supposed difficulty I have found:
>    >  http://hermes.dis.uniroma1.it/~aschaerf/abstracts/ecai-96.html
>    > but I have not actually looked at a copy of the proceedings
>    > described therein.
>    >
>    > Regards,
>    >  -------------------------------------------
>    >  Michael O'Donnell     m o d @ s t d . K o m
>    >  -------------------------------------------
>    >
>    > P.S.  If replying via email please note the  e x p a n d e d
>    >       address supplied in my signature line, where K=3Dc
> 
>    I have an algorithm for generating a schedule. The algorithm is =
> quadratic, so
>    this problem is certainly not NP hard or NP complete. The algorithm =
> took me 3
>    days to come up with, so I also wouldn't say it's trivial. My =
> algorithm is
>    given in the function "roundrobin", below.
> 
>    I coded up the algorithm in C. It asks you for the number of teams, =
> then
>    prints out the schedule. Just to make sure that the schedule is =
> correct,
>    another function checks its validity.
> 
>    Suppose there are n teams. If n is even, then the schedule has n-1 =
> rounds. If
>    n is odd, then the schedule has n rounds, and each team is idle in =
> exactly one
>    round. For example, if n =3D 10, then the schedule is
> 
>    team
>    \      1     2     3     4     5     6     7     8     9    10
>    round \............................................................
>    1:    10     9     8     7     6     5     4     3     2     1
>    2:     6    10     9     8     7     1     5     4     3     2
>    3:     2     1    10     9     8     7     6     5     4     3
>    4:     7     3     2    10     9     8     1     6     5     4
>    5:     3     4     1     2    10     9     8     7     6     5
>    6:     8     5     4     3     2    10     9     1     7     6
>    7:     4     6     5     1     3     2    10     9     8     7
>    8:     9     7     6     5     4     3     2    10     1     8
>    9:     5     8     7     6     1     4     3     2    10     9
> 
>    To read the schedule, notice that each round is listed in a row. So, =
> in round
>    1, team 1 plays team 10, team 2 plays team 9, team 3 plays team 8, =
> team 4
>    plays team 7, and team 5 plays team 6. In round 2, team 1 plays team =
> 6, team 2
>    plays team 10, etc.
> 
>    If n =3D 11, the schedule is:
> 
>    team
>    \      1     2     3     4     5     6     7     8     9    10    11
>    round =
> \..................................................................
>    1:     0    11    10     9     8     7     6     5     4     3     2
>    2:     7     0    11    10     9     8     1     6     5     4     3
>    3:     2     1     0    11    10     9     8     7     6     5     4
>    4:     8     3     2     0    11    10     9     1     7     6     5
>    5:     3     4     1     2     0    11    10     9     8     7     6
>    6:     9     5     4     3     2     0    11    10     1     8     7
>    7:     4     6     5     1     3     2     0    11    10     9     8
>    8:    10     7     6     5     4     3     2     0    11     1     9
>    9:     5     8     7     6     1     4     3     2     0    11    10
>    10:    11     9     8     7     6     5     4     3     2     0     =
> 1
>    11:     6    10     9     8     7     1     5     4     3     2     =
> 0
> 
>    A team being idle is indicated by the schedule listing that it plays =
> team
>    number 0. Notice that team 1 is idle in round 1, team 2 in round 2, =
> etc.
> 
>    The code is given below. The main function reads n and then prints =
> out a nice
>    table. The function "roundrobin" computes the schedule (note that it =
> indexes
>    teams and rounds from 0). The function "check" makes sure that a =
> schedule is
>    valid (by making sure that every team plays every other team; no =
> team plays
>    themselves; each team plays at most once per round; and whenever =
> team i plays
>    team j, then team j also plays team i).
> 
>    Currently, the program has a hard-coded maximum number of teams of =
> 1000. This
>    could easily be increased.
> 
>    Unfortunately, I do not have a proof that my algorithm is correct. =
> I'll try
>    coming up with one, though I probably won't post it here.
>  */
> 
> #include <stdio.h>
> 
> #define MAX 1000
> 
> extern int main(void );
> extern void roundrobin(int (*s)[1000],int n);
> extern int check(int (*s)[1000],int n);
> static int schedule[MAX][MAX]=3D {0} ;
> static int game[MAX][MAX] =3D {0};
> 
> int=20
> main (void)
> {
>   int n, r, i, rounds;
> 
>    /* Input number of teams in the schedule. */
>   printf ("Enter the number of entries that you want a schedule for: =
> ");
>   fflush(stdout);
>   scanf ("%d", &n);
> 
>   /* If the number of teams is even, requires n-1 rounds; if odd, =
> requires n. */
>   if (n % 2)
>     rounds =3D n;
>   else
>     rounds =3D n - 1;
> 
>   roundrobin (schedule, n);
> 
>   /* Print a nice table. */
>   printf ("\n       team\n     \\ ");
>   for (i =3D 0; i < n; i++)
>     printf ("%6d", i + 1);
>   printf ("\n");
>   printf ("round \\");
>   for (i =3D 0; i < 6 * n; i++)
>     printf (".");
>   printf ("\n");
>   for (r =3D 0; r < rounds; r++)
>     {
>       printf ("%6d:", r + 1);
>       for (i =3D 0; i < n; i++)
> 	printf ("%6d", schedule[r][i] + 1);
>       printf ("\n");
>     }
>   printf ("\n");
> 
>   /* Check the schedule and print whether or not it's valid. */
>   if (check (schedule, n))
>     printf ("Schedule is valid.\n");
>   else
>     printf ("Schedule is not valid.\n");
>   return 0;
> }
> 
> /***********************************************************************=
> **
> Compute the round-robin tournament schedule for n teams. If n is even,
> then there are n-1 rounds; if n is odd, there are n rounds and each =
> team
> is idle in exactly one round. A team being idle is indicated by the
> schedule saying that it plays team number -1 in a round.
> ************************************************************************=
> */
> void
> roundrobin (int s[MAX][MAX], int n)
> {
>   int rounds, m, r, i;
> 
>   /* m is the lowest even number greater than or equal to n. */
>   if (n % 2)
>     m =3D n + 1;
>   else
>     m =3D n;
> 
>   /* If the number of teams is even, requires n-1 rounds; if odd, =
> requires n. */
>   if (n % 2)
>     rounds =3D n;
>   else
>     rounds =3D n - 1;
> 
>   /* Fill in the table with a nice diagonal pattern. */
>   for (r =3D 0; r < rounds; r++)
>     {
>       for (i =3D 0; i < r; i++)
> 	s[r][i] =3D ((rounds + r - i + 1) + m) % m;
>       for (i =3D r; i < n; i++)
> 	s[r][i] =3D ((rounds + r - i) + m) % m;
>     }
> 
>   /* Now, do knight-like moves with the 0 in the first row. Every time =
> the 0
>   lands on a number, put that number in the first column. */
>   r =3D 0;
>   for (i =3D m - 2; i > 0; i--)
>     {
>       r =3D ((r - 2) + rounds) % rounds;
>       s[r][0] =3D s[r][i];
>       s[r][i] =3D 0;
>     }
> 
>   /* If m !=3D n, then remove team n from all the games, and replace =
> with -1. */
>   if (m !=3D n)
>     for (i =3D 0; i < rounds; i++)
>       s[i][i] =3D -1;
> }
> 
> /***********************************************************************=
> **
> Looks at a schedule and determines whether it is valid.
> ************************************************************************=
> */
> int=20
> check (int s[MAX][MAX], int n)
> {
>   int rounds, r, i, j;
> 
>   for (i =3D 0; i < n; i++)
>     for (j =3D 0; j < n; j++)
>       game[i][j] =3D 0;
> 
>   /* If the number of teams is even, requires n-1 rounds; if odd, =
> requires n. */
>   if (n % 2)
>     rounds =3D n;
>   else
>     rounds =3D n - 1;
> 
>   /* Count the number of times every team plays every other team. */
>   for (r =3D 0; r < rounds; r++)
>     for (i =3D 0; i < n; i++)
>       {
> 	j =3D s[r][i];
> 	if (j > -1)
> 	  /* A value of -1 would mean that team i is idle this round. */
> 	  {
> 	    /* Record that teams i and j played. */
> 	    game[i][j]++;
> 	    game[j][i]++;
> 	    /* Note that we will double-count the games, because we
> 	     * record it when team i plays j, as well as when j plays i. */
> 	  }
>       }
> 
>   /* Make sure that every pair played exactly once, and nobody ever =
> played
>   themselves. */
>   for (i =3D 0; i < n; i++)
>     {
>       if (game[i][i] !=3D 0)
> 	/* If a team plays themselves, it's not a valid schedule. */
> 	{
> 	  printf ("Team %d played itself.\n", i);
> 	  return 0;
> 	}
>       for (j =3D i + 1; j < n; j++)
> 	/* We have to check for a 2, because games are double-counted. */
> 	if (game[i][j] !=3D 2)
> 	  /* If two teams didn't play exactly one time, it's not valid. */
> 	  return 0;
>     }
> 
>   /* Make sure that each team plays at most once per round. */
>   for (r =3D 0; r < rounds; r++)
>     {
>       /* We will use game[0] to count the number of times each team =
> appears
>        * in a round. */
>       for (i =3D 0; i < n; i++)
> 	game[0][i] =3D 0;
>       /* Count number of times each teams appears in round r. */
>       for (i =3D 0; i < n; i++)
> 	{
> 	  j =3D s[r][i];
> 	  /* Team i played team j in round r. */
> 	  if (j >=3D 0)
> 	    /* -1 means that team i was idle this round. */
> 	    game[0][j]++;
> 	}
>       /* Make sure each team appears at most once. */
>       for (i =3D 0; i < n; i++)
> 	if (game[0][i] > 1)
> 	  /* Team i appeared more than once in round r. Not valid. */
> 	  return 0;
>     }
> 
>   /* Make sure that when team i plays team j, team j also plays team i. =
> */
>   for (r =3D 0; r < rounds; r++)
>     for (i =3D 0; i < n; i++)
>       {
> 	j =3D s[r][i];
> 	/* Team i played team j in round r. */
> 	if (j >=3D 0)
> 	  /* -1 means that team i was idle this round. */
> 	  if (s[r][j] !=3D i)
> 	    /* If team j didn't play team i, not valid. */
> 	    return 0;
>       }
> 
>   /* Otherwise, the schedule is valid. */
>   return 1;
> }
> 
> ------_=_NextPart_000_01BF78BA.EEC5A566--
>