Round-robin tournament schedule: Difference between revisions
Content added Content deleted
(Added Go) |
|||
Line 466: | Line 466: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</lang>--> |
<!--</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}}== |
=={{header|Raku}}== |