Re: a challenge/problem.
- To: mathgroup at smc.vnet.net
- Subject: [mg40120] Re: a challenge/problem.
- From: "Daniel Lidström" <daniel.lidstrom at _DELETE_home.se>
- Date: Fri, 21 Mar 2003 02:37:59 -0500 (EST)
- References: <b56hga$bve$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Simon... wrote:
> Hi,
>
> I've got a puzzle, im not sure how to solve, a friend of mine asked
> me to make a program that given a number of teams (which must be more
> than 4 but other than that just dividable by 2) - now, there is
> teams\2 matches in a round, and no team must play more than 1 match
> in a round (making the number of rounds teams-1).
>
> so if there is 10 teams, then there is 9 rounds, and 5 matches in each
> round, with a total of 45 matches.
>
> a list of combined matches could look like this
>
> 10 vs. 9
> 10 vs. 8
> 10 vs. 7
> 10 vs. 6
> 10 vs. 5
> 10 vs. 4
> 10 vs. 3
> 10 vs. 2
> 10 vs. 1
> 9 vs. 8
> 9 vs. 7
> 9 vs. 6
> 9 vs. 5
> 9 vs. 4
> 9 vs. 3
> 9 vs. 2
> 9 vs. 1
> 8 vs. 7
> 8 vs. 6
> 8 vs. 5
> 8 vs. 4
> 8 vs. 3
> 8 vs. 2
> 8 vs. 1
> 7 vs. 6
> 7 vs. 5
> 7 vs. 4
> 7 vs. 3
> 7 vs. 2
> 7 vs. 1
> 6 vs. 5
> 6 vs. 4
> 6 vs. 3
> 6 vs. 2
> 6 vs. 1
> 5 vs. 4
> 5 vs. 3
> 5 vs. 2
> 5 vs. 1
> 4 vs. 3
> 4 vs. 2
> 4 vs. 1
> 3 vs. 2
> 3 vs. 1
> 2 vs. 1
>
> which was generated with this algorithm (which is perl if you should
> be interested):
>
> #make the ordered list of matches
> $current = $teams; #current is now = 10
> while ($current > 1)
> {
> $next_team = $current-1;
>
> while ($next_team >= 1)
> {
> $matches[$counter] = "$current vs. $next_team"; #array
> to hold the matches
> $counter++;
> $next_team--;
> }
> $current--;
> }
>
>
> now how do i make the teams-1 rounds with 5 matches in each, where a
> team does not play 2 matches.... ??
This is called a RoundRobin tournament. Here is a piece of C code that does
what you asked for:
/*
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: [mg40120] Re: RoundRobin tournament problem solvable?
Author: Adam Florence <aflorenc at acm.org>
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=c
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 = 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 = 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]= {0} ;
static int game[MAX][MAX] = {0};
int
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 = n;
else
rounds = n - 1;
roundrobin (schedule, n);
/* Print a nice table. */
printf ("\n team\n \\ ");
for (i = 0; i < n; i++)
printf ("%6d", i + 1);
printf ("\n");
printf ("round \\");
for (i = 0; i < 6 * n; i++)
printf (".");
printf ("\n");
for (r = 0; r < rounds; r++)
{
printf ("%6d:", r + 1);
for (i = 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 = n + 1;
else
m = n;
/* If the number of teams is even, requires n-1 rounds; if odd, requires
n. */
if (n % 2)
rounds = n;
else
rounds = n - 1;
/* Fill in the table with a nice diagonal pattern. */
for (r = 0; r < rounds; r++)
{
for (i = 0; i < r; i++)
s[r][i] = ((rounds + r - i + 1) + m) % m;
for (i = r; i < n; i++)
s[r][i] = ((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 = 0;
for (i = m - 2; i > 0; i--)
{
r = ((r - 2) + rounds) % rounds;
s[r][0] = s[r][i];
s[r][i] = 0;
}
/* If m != n, then remove team n from all the games, and replace with -1.
*/
if (m != n)
for (i = 0; i < rounds; i++)
s[i][i] = -1;
}
/*************************************************************************
Looks at a schedule and determines whether it is valid.
*************************************************************************/
int
check (int s[MAX][MAX], int n)
{
int rounds, r, i, j;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
game[i][j] = 0;
/* If the number of teams is even, requires n-1 rounds; if odd, requires
n. */
if (n % 2)
rounds = n;
else
rounds = n - 1;
/* Count the number of times every team plays every other team. */
for (r = 0; r < rounds; r++)
for (i = 0; i < n; i++)
{
j = 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 = 0; i < n; i++)
{
if (game[i][i] != 0)
/* If a team plays themselves, it's not a valid schedule. */
{
printf ("Team %d played itself.\n", i);
return 0;
}
for (j = i + 1; j < n; j++)
/* We have to check for a 2, because games are double-counted. */
if (game[i][j] != 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 = 0; r < rounds; r++)
{
/* We will use game[0] to count the number of times each team appears
* in a round. */
for (i = 0; i < n; i++)
game[0][i] = 0;
/* Count number of times each teams appears in round r. */
for (i = 0; i < n; i++)
{
j = s[r][i];
/* Team i played team j in round r. */
if (j >= 0)
/* -1 means that team i was idle this round. */
game[0][j]++;
}
/* Make sure each team appears at most once. */
for (i = 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 = 0; r < rounds; r++)
for (i = 0; i < n; i++)
{
j = s[r][i];
/* Team i played team j in round r. */
if (j >= 0)
/* -1 means that team i was idle this round. */
if (s[r][j] != i)
/* If team j didn't play team i, not valid. */
return 0;
}
/* Otherwise, the schedule is valid. */
return 1;
}