Consider the design of a round robin tennis tournament schedule for n = 2^k play
ID: 3667747 • Letter: C
Question
Consider the design of a round robin tennis tournament schedule for n = 2^k players. Each player must play every other player, and each player must play one match per day for n - 1 days, the minimum number of days needed to complete the tournament. The tournament schedule is thus an n row by n - 1 column table whose entry in row i and column j is the player i must content with on the j^th day. The divide-and-conquer approach constructs a schedule for one-half of the players. This schedule is designed by a recursive application of the algorithm by finding a schedule for one half of these players and so on. When we get down to two players, we have the base case and simply pair them up. Suppose there are eight players. The schedule for player 1 through 4 fills the upper left corner (4 rows by 3 columns) of the schedule being constructed. The lower left corner (4 rows by 3 columns) of the schedule must pit the high numbered players (5 through 8) against one another. This subschedule is obtained by adding 4 to each entry in the upper left. We have now simplified the problem. All that remains is to have the lower-numbered player play high-numbered players. This is easily accomplished by having players 1 through 4 play 5 through 8, respectively, on day 4, and cyclically permuting 5 through 8 on subsequent days. Round robin schedules for two, four, and eight players are given below. You should now be able to generalize the ideas to write pseudocode for a divide-and-conquer algorithm to produce a round robin tennis tournament schedule for 2^k players for any k.Explanation / Answer
Sample Prolog solution, using SWI-Prolog:
:- use_module(library(clpfd)).
tennis(N, Courts, Rows) :-
length(Rows, N),
maplist(same_length(Rows), Rows),
transpose(Rows, Rows),
Rows = [[_|First]|_],
chain(First, #<),
length(_, MaxRounds),
numlist(1, MaxRounds, Rounds),
pairs_keys_values(Pairs, Rounds, Counts),
Counts ins 0..Courts,
foldl(triangle, Rows, Vss, Dss, 0, _),
append(Vss, Vs),
global_cardinality(Vs, Pairs),
maplist(breaks, Dss),
labeling([ff], Vs).
triangle(Row, Vs, Ds, N0, N) :-
length(Prefix, N0),
append(Prefix, [-|Vs], Row),
append(Prefix, Vs, Ds),
N #= N0 + 1.
breaks([]).
breaks([P|Ps]) :- maplist(breaks_(P), Ps), breaks(Ps).
breaks_(P0, P) :- abs(P0-P) #> 1.
Sample query: 5 players on 2 courts:
?- time(tennis(5, 2, Rows)), maplist(writeln, Rows).
% 827,838 inferences, 0.257 CPU in 0.270 seconds (95% CPU, 3223518 Lips)
[-,1,3,5,7]
[1,-,5,7,9]
[3,5,-,9,1]
[5,7,9,-,3]
[7,9,1,3,-]
The specified task, 6 players on 2 courts, solved well within the time limit of 1 minute:
?- time(tennis(6, 2, Rows)), maplist(writeln, Rows).
% 5,605,107 inferences, 1.775 CPU in 2.137 seconds (83% CPU, 3156941 Lips)
[-,1,3,5,7,10]
[1,-,6,9,11,3]
[3,6,-,11,9,1]
[5,9,11,-,2,7]
[7,11,9,2,-,5]
[10,3,1,7,5,-]
Further example: 7 players on 5 courts:
?- time(tennis(7, 5, Rows)), maplist(writeln, Rows).
% 105,563,012 inferences, 35.757 CPU in 46.680 seconds (77% CPU, 2952225 Lips)
[-,1,3,5,7,9,11]
[1,-,5,3,11,13,9]
[3,5,-,9,1,7,13]
[5,3,9,-,13,11,7]
[7,11,1,13,-,5,3]
[9,13,7,11,5,-,1]
[11,9,13,7,3,1,-]