Round-robin tournament schedule: Difference between revisions
→{{header|Picat}}
(Added Go) |
|||
Line 466:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
=={{header|Picat}}==
===Constraint modelling===
<lang Picat>import sat.
main =>
nolog,
N = 12,
tournament_cp(N, NumRounds,NumPairs,_,X,Bye),
print_tournament(X,NumRounds,NumPairs,Bye),
nl.
tournament_cp(N, NumRounds,NumPairs,Extras, X,Bye) =>
% Adjust for odd number of players.
% The bye (Dummy) player is N+1.
if N mod 2 == 1 then
N := N + 1,
Bye = N
end,
NumRounds = N-1,
NumPairs = N div 2,
X = new_array(NumRounds,NumPairs,2),
X :: 1..N,
% ensure that all players play each other
foreach(P1 in 1..N, P2 in P1+1..N)
sum([X[Round,P,1] #= P1 #/\ X[Round,P,2] #= P2 : Round in 1..NumRounds, P in 1..NumPairs]) #= 1
end,
foreach(Round in 1..NumRounds)
all_different([X[Round,I,J] : I in 1..NumPairs, J in 1..2]),
% symmetry breaking
% - all first players in increasing order
increasing_strict([X[Round,I,1] : I in 1..NumPairs]),
% - player 1 < player 2
foreach(P in 1..NumPairs)
X[Round,P,1] #< X[Round,P,2]
end
end,
if Extras != [] then
foreach([P1,P2,Round] in Extras)
sum([X[Round,P,1] #= P1 #/\ X[Round,P,2] #= P2 : P in 1..NumPairs]) #= 1
end
end,
solve($[ff,split],X).
print_tournament(X,NumRounds,NumPairs,Bye) =>
N = X[1].len,
foreach(Round in 1..NumRounds)
printf("Round %2d: ", Round),
if N > 10 then nl end,
foreach(P in 1..NumPairs)
P2Val = X[Round,P,2],
if var(Bye) ; P2Val != Bye then
printf("(%2w vs %2w) ",X[Round,P,1],P2Val),
if N > 10 then nl end
end
end,
nl
end,
nl.</lang>
{{out}}
<pre>Round 1: ( 1 vs 11) ( 2 vs 5) ( 3 vs 6) ( 4 vs 12) ( 7 vs 9) ( 8 vs 10)
Round 2: ( 1 vs 5) ( 2 vs 4) ( 3 vs 10) ( 6 vs 7) ( 8 vs 9) (11 vs 12)
Round 3: ( 1 vs 6) ( 2 vs 8) ( 3 vs 5) ( 4 vs 11) ( 7 vs 10) ( 9 vs 12)
Round 4: ( 1 vs 12) ( 2 vs 11) ( 3 vs 7) ( 4 vs 6) ( 5 vs 8) ( 9 vs 10)
Round 5: ( 1 vs 9) ( 2 vs 6) ( 3 vs 12) ( 4 vs 5) ( 7 vs 8) (10 vs 11)
Round 6: ( 1 vs 4) ( 2 vs 3) ( 5 vs 7) ( 6 vs 10) ( 8 vs 12) ( 9 vs 11)
Round 7: ( 1 vs 2) ( 3 vs 4) ( 5 vs 10) ( 6 vs 9) ( 7 vs 12) ( 8 vs 11)
Round 8: ( 1 vs 3) ( 2 vs 12) ( 4 vs 10) ( 5 vs 9) ( 6 vs 8) ( 7 vs 11)
Round 9: ( 1 vs 10) ( 2 vs 7) ( 3 vs 8) ( 4 vs 9) ( 5 vs 11) ( 6 vs 12)
Round 10: ( 1 vs 8) ( 2 vs 10) ( 3 vs 9) ( 4 vs 7) ( 5 vs 12) ( 6 vs 11)
Round 11: ( 1 vs 7) ( 2 vs 9) ( 3 vs 11) ( 4 vs 8) ( 5 vs 6) (10 vs 12) </pre>
===Constraint model with extra constraints===
The constraint model is slower than the algorithmic approach for larger number of players. The advantage of a constraint model is that it is quite easy to add extra constraint, such that some players must play in a certain round (e.g. for availability reasons etc).
Here are some extra constraints:
* 1 vs 2 must be played the third round
* 5 vs 9 must be played in the 7th round
* 2 vs 3 must be played in the last round
* 7 vs 12 must be played in the last round
<lang Picat>main =>
nolog,
N = 12,
Extras = [[1,2,3],
[5,9,7],
[2,3,N-1],
[7,12,N-1]],
tournament_cp(N, NumRounds,NumPairs,Extras,X,Bye),
print_tournament(X,NumRounds,NumPairs,Bye).</lang>
{{out}}
<pre>Round 1: ( 1 vs 11) ( 2 vs 4) ( 3 vs 12) ( 5 vs 8) ( 6 vs 9) ( 7 vs 10)
Round 2: ( 1 vs 12) ( 2 vs 11) ( 3 vs 9) ( 4 vs 7) ( 5 vs 10) ( 6 vs 8)
Round 3: ( 1 vs 2) ( 3 vs 10) ( 4 vs 12) ( 5 vs 11) ( 6 vs 7) ( 8 vs 9)
Round 4: ( 1 vs 4) ( 2 vs 6) ( 3 vs 11) ( 5 vs 12) ( 7 vs 8) ( 9 vs 10)
Round 5: ( 1 vs 10) ( 2 vs 7) ( 3 vs 5) ( 4 vs 6) ( 8 vs 12) ( 9 vs 11)
Round 6: ( 1 vs 6) ( 2 vs 5) ( 3 vs 4) ( 7 vs 9) ( 8 vs 11) (10 vs 12)
Round 7: ( 1 vs 3) ( 2 vs 12) ( 4 vs 8) ( 5 vs 9) ( 6 vs 10) ( 7 vs 11)
Round 8: ( 1 vs 7) ( 2 vs 8) ( 3 vs 6) ( 4 vs 5) ( 9 vs 12) (10 vs 11)
Round 9: ( 1 vs 8) ( 2 vs 9) ( 3 vs 7) ( 4 vs 10) ( 5 vs 6) (11 vs 12)
Round 10: ( 1 vs 9) ( 2 vs 10) ( 3 vs 8) ( 4 vs 11) ( 5 vs 7) ( 6 vs 12)
Round 11: ( 1 vs 5) ( 2 vs 3) ( 4 vs 9) ( 6 vs 11) ( 7 vs 12) ( 8 vs 10) </pre>
For this small tournament it took about the same time with and without these extra constraints (0.08s).
===Number of solutions===
Here are the number of different solutions for N = [2,4,6,8] with the symmetry constraints (but without the extra round constraints). The number of odd N players is the same as the number of N-1 players.
Here the cp solver is used since it's faster than the sat solver for generating all solutions.
<lang Picat>import cp.
main =>
foreach(N in 2..2..8)
Count = count_all(tournament_cp(N, _NumRounds,_NumPairs,_Extras,_X,_Bye)),
println(N=Count)
end.</lang>
{{out}}
<pre>2 = 1
4 = 6
6 = 720
8 = 31449600</pre>
This seems to be related to the OEIS sequence [https://oeis.org/A036981 "A036981: (2n+1) X (2n+1) symmetric matrices each of whose rows is a permutation of 1..(2n+1)"]. The next term (for N=10) would be 444733651353600 which takes too long to check.
=={{header|Raku}}==
| |||