[mod.computers.workstations] Subject: League planning

Jacob_Palme_QZ@QZCOM.MAILNET (01/11/86)

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 for 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.

works@ucbvax.UUCP (01/13/86)

For what its worth, I recall reading an article in Sports Illustrated
about a couple who do the scheduling for major league baseball using
a mini-computer (I think).  While there were no technical details, if
you call/write SI, they might give you the names of the people
involved.  I think the article came out sometime in 1985.  Good luck.

                                Tim Peacock

works@ucbvax.UUCP (01/14/86)

> From: Jacob_Palme_QZ%QZCOM.MAILNET@MIT-MULTICS.ARPA
> 
> 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.

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