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