総当たり戦の日程作成 in Prolog DouKaku?

総当たり戦の日程作成

任意の偶数Nのチームの総当たり戦を最短日数（N-1日）で行う場合の日程表を１つ作成してください。

解はひとつではない場合もあります。
もし、余力があれば、全ての可能性も求めてください。

これは、スポーツスケジューリングと言う分野の問題で、数学的には、カークマンの問題と言うのが近いようです。

例えば、４チームであれば、

1-2 3-4
1-3 2-4
1-4 2-3

６チームであれば

1-2 3-4 5-6 
1-3 2-5 4-6 
1-4 2-6 3-5 
1-5 2-4 3-6 
1-6 2-3 4-5

が解のひとつです。

see: カークマンの組分け

post comment

Posted feedbacks - Prolog

日にちだけの入れ替えを除いて，全通り出力．並びが逆になってるので見づらいですが．
4 teams
[[2-3, 1-4], [2-4, 1-3], [3-4, 1-2]]
6 teams
[[4-5, 2-3, 1-6], [3-6, 2-4, 1-5], [3-5, 2-6, 1-4], [4-6, 2-5, 1-3], [5-6, 3-4, 1-2]]
[[4-5, 2-3, 1-6], [3-4, 2-6, 1-5], [3-6, 2-5, 1-4], [5-6, 2-4, 1-3], [4-6, 3-5, 1-2]]
[[3-5, 2-4, 1-6], [4-6, 2-3, 1-5], [3-6, 2-5, 1-4], [4-5, 2-6, 1-3], [5-6, 3-4, 1-2]]
[[3-4, 2-5, 1-6], [4-6, 2-3, 1-5], [3-5, 2-6, 1-4], [5-6, 2-4, 1-3], [4-5, 3-6, 1-2]]
[[3-5, 2-4, 1-6], [3-4, 2-6, 1-5], [5-6, 2-3, 1-4], [4-6, 2-5, 1-3], [4-5, 3-6, 1-2]]
[[3-4, 2-5, 1-6], [3-6, 2-4, 1-5], [5-6, 2-3, 1-4], [4-5, 2-6, 1-3], [4-6, 3-5, 1-2]]

match([_], []).
match([X|Xs], Ys) :-
    group_pairs_by_key(Y, [X-Xs]), append(Y, Y1, Ys), match(Xs, Y1).

game([], G, G).
game([X1-X2|Xs], Ys, G) :-
    append(Y1, [Y|Y2], Ys), \+ memberchk(Y, Y2),
    \+ memberchk(X1-_, Y), \+ memberchk(_-X1, Y),
    \+ memberchk(X2-_, Y), \+ memberchk(_-X2, Y),
    append(Y1, [[X1-X2|Y]|Y2], Z), game(Xs, Z, G).

round_robin(N, G) :- N mod 2 =:= 0,
    numlist(1, N, X), match(X, Y), N1 is N - 1,
    length(G0, N1), maplist(ord_empty, G0), game(Y, G0, G).

:-  writeln('4 teams'), forall(round_robin(4, G), writeln(G)),
    writeln('6 teams'), forall(round_robin(6, G), writeln(G)).

DouKaku?

総当たり戦の日程作成

Posted feedbacks - Prolog

Index

Feed

Other

Link

Pathtraq