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; }