Subject: League planning
Jacob_P...@qzcom.mailnet
I have a programming problem I have not been able to solve. Perhaps
someone else has already solved it?
My problem is that I want to make a plan f|r a league of teams
to play e.g. soccer or ice-hockey.
Such a league consists of an even number of teams, between 4
and 18 teams in a league. Each team is to meet each other team
twice, one at home and one at home of the other team.
Thus, the number of days will be N*(N-1)*2 if N is the number
of teams. Each day, N/2 games will be played between the teams.
Additional restrictions: As much as possible, every second day
for a team should be a game at home and every second a game at
home for the other team. At least, a team should never have to
play three games in succession at home or not at home.
Also, if two teams from the same city meet, then a possible third
team from the same city should not play at home the same day.
Meetings between teams from the same city should not be in the
beginning and the end of the league.
Does anyone know of any existing software, public or commercial,
which solves this problem? Or does anyone know of a good algorithm.
I have tried with heuristic problem solving techniques, and can
get it working for small leagues of up to 8 teams, but can not
get my program to converge on an acceptable solution for larger
league sizes.
Mark A. Ardis
There is a well-known algorithm for scheduling round-robin
tournaments:
1) Arrange teams in two columns (initial positions do not matter).
For example:
A vs. B
C vs. D
E vs. F
G vs. H
2) For each round, rotate all but one of the teams (direction does
not matter, but must be consistent). For example:
A vs. C
E vs. B
G vs. D
H vs. F
A vs. E
G vs. C
H vs. B
F vs. D
etc.
For your problem, a modified version of this algorithm may be
constructed:
1) (Same as above).
2) Play each round as constructed in the previous algorithm twice in
succesion, but reverse the home team for the second match. For
example:
Home Away
A vs. B
C vs. D
E vs. F
G vs. H
Away Home
A vs. B
C vs. D
E vs. F
G vs. H
Home Away
A vs. C
E vs. B
G vs. D
H vs. F
Away Home
A vs. C
E vs. B
G vs. D
H vs. F
Home Away
A vs. E
G vs. C
H vs. B
F vs. D
Away Home
A vs. E
G vs. C
H vs. B
F vs. D
etc.
This algorithm guarantees that no team will play 3 games in a row at
home, and no team will play 3 games in a row away. (If your concept
of "at home" means "in the home city" this is not guaranteed. The
algorithm only guarantees proper behavior for "home field".) For
large leagues the pattern will usually be: home-away-home-away-... If
you set the initial configuration properly, you may be able to satisfy
the constraint about "same city" teams.
Here is an implementation of the original algorithm in Pascal:
program tourney(input, output);
{A program to compute round-robin tournament pairings.}
const
MAXN = 50; { Largest size of tournament (in players) }
MAXHALF = 25;
type
Playertype = 1 .. MAXN;
Halftype = 1 .. MAXHALF;
var
n : Playertype;
half : Halftype;
a, b : array[Halftype] of Playertype;
i : Playertype;
{***********************************************************}
{Display one round of round-robin tournament.}
procedure Display(round : Playertype);
var
i : Halftype;
begin
writeln('Round:', round);
writeln ;
for i := 1 to half do
writeln(a[i]:3, ' versus', b[i]:3);
writeln
end;
{***********************************************************}
{Create initial round of round-robin tournament.}
procedure Initialize;
var
x : integer;
i : Halftype;
begin
writeln('Number of players:');
read(x);
if x mod 2 = 0 then
n := x
else
begin
n := x + 1;
writeln('Rounding up to', n:3, '(=BYE)')
end;
half := n div 2;
for i := 1 to half do
begin
a[i] := i;
b[i] := i + half
end;
Display(1)
end;
{***********************************************************}
{Rotate list of players for next round of round-robin tournament.}
procedure Rotate;
var
temp : Playertype;
i : Halftype;
begin
temp := b[1];
for i := 1 to half - 1 do
b[i] := b[i + 1];
b[half] := a[half];
for i := half downto 3 do
a[i] := a[i - 1];
a[2] := temp
end;
{********** Main Program **********}
begin
Initialize;
for i := 2 to n do
begin
Rotate;
writeln('lkjlkj');
Display(i)
end;
writeln('End of tourney.')
end.
--
Mark A. Ardis ardis%wanginst@CSNet-Relay (CSNet)
Wang Institute of Graduate Studies ...!decvax!wanginst!ardis (UUCP)
Tyng Road, Tyngsboro, MA 01879 (617) 649-9731