a challenge/problem.
Simon...
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.... ??
Thanks for any help !
Kindly
-Simon
ps. this message is posted to various math groups.
Wolf, Hartmut
Simon,
it's not quite clear to me, what you finally want to know. Anyway, you may
translate that perl code quite literally to Mathematica:
In[56]:= $teams = 10;
In[57]:=
(* make the ordered list of matches *)
$current = $teams; (* current is now = 10 *)
$counter = 1; Clear[$matches];
While[ ($current > 1),
($nextTeam = $current - 1;
While[ ($nextTeam >= 1) , ($matches[$counter] =
ToString[$current] <> " vs. " <> ToString[$nextTeam];(*
array to hold the matches *)
$counter++;
$nextTeam--;) ];
$current--;)]
In[60]:= Array[$matches, {$teams*($teams - 1)/2}] // TableForm
This just gives that list of pairings (matches) above. You may run that code
with any number of teams, e.g. $Teams = 11 or 0, 1, 2, 3, ...
It does not give the matches grouped into rounds however. For that there are
more possible solutions.
What we did, when playing an impromptu quick chess tournament, was this:
align all tables in the room to a row, put the chess-boards onto the table
in alternating orientation of white and black. Of course chairs were placed
accordingly.
Now depending on the number of players:
If they were odd, an additional chair was put at the head of the row of
tables. Then we took place at the boards, one person offside at the head,
and tack, tack, tack,... moved the chess-men. After at most 10 minutes, all
games were over, we put up the fallen kings and all their royal househould,
and each of us moved a chair clockwise (now a different person at the head,
if any). The tournament was over, when everyone arrived at his or her
starting seat.
If the number of players, where even, then no extra chair was needed, of
course, but then the player #1 kept his seat and didn't move up, whereas all
others rotated. Instead player #1 had to turn the chessboard after every
game.
This translates to Mathematica:
In[157]:=
rounds[nteams_Integer?EvenQ] /; nteams > 1 :=
Module[{t = Range[nteams]},
MapIndexed[
Module[{evenround = EvenQ[First[#2]]},
Prepend[MapIndexed[
Inner[#1[#2] &,
If[EvenQ[First[#2]] || evenround && First[#2] === 1,
Reverse, Identity][{White, Black}], #1, List] &,
Transpose[MapAt[Reverse, Partition[#1, Floor[nteams/2]],
2]]],
"Round " <> ToString[First[#2]] <> ":"]] &,
Table[Prepend[RotateRight[Rest[t], r], First[t]], {r, 0,
nteams - 2}]]] // TableForm
In[158]:=
rounds[nteams_Integer?OddQ] /; nteams > 1 :=
Module[{t = Range[nteams]},
MapIndexed[
Prepend[MapIndexed[
Inner[#1[#2] &,
If[EvenQ[First[#2]], Reverse, Identity][{White, Black}],
#1,
List] &,
Transpose[MapAt[Reverse, Partition[#, Floor[nteams/2]], 2]]],
"Round " <> ToString[First[#2]] <> ":"] &,
Table[RotateRight[t, r], {r, 0, nteams - 1}]]] // TableForm
In[159]:= rounds[8]
Out[159]//TableForm=
Round 1: White[1] Black[2] White[3] Black[4]
Black[8] White[7] Black[6] White[5]
Round 2: Black[1] Black[8] White[2] Black[3]
White[7] White[6] Black[5] White[4]
Round 3: White[1] Black[7] White[8] Black[2]
Black[6] White[5] Black[4] White[3]
Round 4: Black[1] Black[6] White[7] Black[8]
White[5] White[4] Black[3] White[2]
Round 5: White[1] Black[5] White[6] Black[7]
Black[4] White[3] Black[2] White[8]
Round 6: Black[1] Black[4] White[5] Black[6]
White[3] White[2] Black[8] White[7]
Round 7: White[1] Black[3] White[4] Black[5]
Black[2] White[8] Black[7] White[6]
In[160]:= rounds[9]
Out[160]//TableForm=
Round 1: White[1] Black[2] White[3] Black[4]
Black[8] White[7] Black[6] White[5]
Round 2: White[9] Black[1] White[2] Black[3]
Black[7] White[6] Black[5] White[4]
Round 3: White[8] Black[9] White[1] Black[2]
Black[6] White[5] Black[4] White[3]
Round 4: White[7] Black[8] White[9] Black[1]
Black[5] White[4] Black[3] White[2]
Round 5: White[6] Black[7] White[8] Black[9]
Black[4] White[3] Black[2] White[1]
Round 6: White[5] Black[6] White[7] Black[8]
Black[3] White[2] Black[1] White[9]
Round 7: White[4] Black[5] White[6] Black[7]
Black[2] White[1] Black[9] White[8]
Round 8: White[3] Black[4] White[5] Black[6]
Black[1] White[9] White[8] White[7]
Round 9: White[2] Black[3] White[4] Black[5]
Black[9] White[8] Black[7] White[6]
--
Hartmut Wolf
Daniel Lidström
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: Re: RoundRobin tournament problem solvable?
Author: Adam Florence <aflo...@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;
}
Paul Abbott
> 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).
There is a Mathematica Notebook at
http://mathworld.wolfram.com/Tournament.html
which gives graphical (pun intended) representations of tournaments.
Cheers,
Paul
--
Paul Abbott Phone: +61 8 9380 2734
School of Physics, M013 Fax: +61 8 9380 1014
The University of Western Australia (CRICOS Provider No 00126G)
35 Stirling Highway
Crawley WA 6009 mailto:pa...@physics.uwa.edu.au
AUSTRALIA http://physics.uwa.edu.au/~paul
Dr Bob
Perhaps I'm missing something, but these graphs seem to contain no
information about how games are arranged in time. They merely record the
results, in terms of who beat whom in each possible pairing. Nor are
"score sequences" of any use for laying out a tournament, despite the term
"sequence" that sometimes indicates ordering or chronology (but not in this
case).
So... I'm not sure I can agree that these are graphical representations of
tournaments.
I am in favor of Swiss system tournaments (commonly used in Chess matches),
rather than the exhaustive (and inefficient) tournaments we're talking
about here.
Swiss system tournaments match up roughly comparable opponents in each
round, so that at the end, we don't have controversies about how tough each
team's schedule was. The result would be NBA or football playoffs that
include the best teams. The down-sides are (1) that the schedule couldn't
be determined before the season begins, and (2) by mid-season, losers would
be playing losers, so those games would probably be canceled if ticket
sales are the goal.
The latter is a down-side only for losing teams, however --- but a big plus
for fans.
Bobby
On Sat, 22 Mar 2003 05:08:30 -0500 (EST), Paul Abbott
<pa...@physics.uwa.edu.au> wrote:
> Simon wrote:
>
>> 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).
>
> There is a Mathematica Notebook at
>
> http://mathworld.wolfram.com/Tournament.html
>
> which gives graphical (pun intended) representations of tournaments.
> Cheers,
> Paul
>
--
maj...@cox-internet.com
Bobby R. Treat