スポーツリーグのスケジュールを自動生成する方法
https://stackoverflow.com/questions/1037057
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
このトピックは複雑であり、おそらく簡単な答えはないことを理解していると言うことから始めます。それが簡単であれば、誰もがそれをやっているでしょう。言われていること...
スポーツリーグを管理するためのアプリケーションの作成を求められました。コンセプトのほとんどは、これを除いて非常に理解しやすいです：重複のないプレイのスケジュールを生成する方法（チームは一度に2チームをプレイします）他の部門を1回、スケジュールに穴がないことを確認します（各チームは毎週プレーします）
現在、この目的を果たすために作成したロゼッタストーンタイプのスプレッドシートを使用してプロセスが手動で行われますが、設計されたチームの数でのみ機能します。 30チーム、24チーム、28チームのバリエーションがあります。変換テーブルを継続的に再調整しようとするのではなく、そのロジックを体系化し、代わりにそのプロセスを微調整できるようにしたいと思います。
思考？
解決
たとえば、ラウンドロビンと呼ばれるチェスのトーナメント。
アイデアは、プレイヤーをテーブルの両側に分割することです。プレーヤーの1人は「ハブ」として指定されています。 （より良い言葉が欲しい場合）。トーナメントは、プレイヤー同士が対戦することから始まります。最初のラウンドの後、ハブを除く全員が1つの椅子を前に移動し、ホワイト/ブラック（スポーツではホーム/アウェイ）の順序が切り替わります。ラウンドロビン競技全体は、プレーヤーが元の場所に着いたときに終了します。全員に2回プレイしてもらいたい場合は、もう一度同じことをしてください。
ウィキペディアの記事と実装の詳細。
特別な場合には、すべてのチームを含めてラウンドロビンを一度実行してみます。その後、各ディビジョンで同じことを行い、ディビジョン内のチームがホームで1度、そして一度離れてお互いにプレーできるように、そのラウンドでチームがどのようにプレーしたかを最初のラウンドロビンから確認します。
これの欠点は、もちろん、トーナメントが終了するかなり前にすべての部門間試合をプレイすることです（最後のn-1試合は部門内チームに対して行われるためです[n =部門内のチームの数]）。これが問題になる場合は、単に一致を少し入れ替えることができます。
実際にこれを行う簡単なPythonスクリプトを作成しました。多くのコード行は必要なく、かなり良い結果が得られました。これにより、各チームが各部門の各チームを他の部門のチームと2回ずつ対戦するスケジュールが作成されます。ただし、同じチームが家にいるような方法で、チームが互いに2回会うことを確認するチェックはありません。ただし、このコードは、独自のスケジューリングコードを作成する方法について良いアイデアを提供するはずです。
#!/usr/bin/python
div1 = ["Lions", "Tigers", "Jaguars", "Cougars"]
div2 = ["Whales", "Sharks", "Piranhas", "Alligators"]
div3 = ["Cubs", "Kittens", "Puppies", "Calfs"]
def create_schedule(list):
""" Create a schedule for the teams in the list and return it"""
s = []
if len(list) % 2 == 1: list = list + ["BYE"]
for i in range(len(list)-1):
mid = int(len(list) / 2)
l1 = list[:mid]
l2 = list[mid:]
l2.reverse()
# Switch sides after each round
if(i % 2 == 1):
s = s + [ zip(l1, l2) ]
else:
s = s + [ zip(l2, l1) ]
list.insert(1, list.pop())
return s
def main():
for round in create_schedule(div1):
for match in round:
print match[0] + " - " + match[1]
print
for round in create_schedule(div2):
for match in round:
print match[0] + " - " + match[1]
print
for round in create_schedule(div3):
for match in round:
print match[0] + " - " + match[1]
print
for round in create_schedule(div1+div2+div3):
for match in round:
print match[0] + " - " + match[1]
print
if __name__ == "__main__":
main()
他のヒント
ラウンドロビンを確実に行うために、奇数チーム用と偶数チーム用の2つのアルゴリズムがあります。
可能な場合は、グラフィックを生成します。
ODDチーム数
アルゴリズムは、すべてのチームを時計回りに回転させることです。 5つのチームがある場合：
1 2 --> 3 1 --> 5 3 --> 4 5 --> 2 4
3 4 5 2 4 1 2 3 1 5
5 4 2 1 3
この時点で、1回のラウンドロビンが完了し、全員が1回プレイします。次のラウンドは再び行われます。
1 2
3 4
5
偶数チーム＃
偶数のチームがある場合、チーム＃1を固定位置に保持し、他のすべてのチームを＃1の周りに時計回りに回転させることを除いて、同じローテーションを行います。したがって、4つのチームがある場合..
1 2 --> 1 3 --> 1 4
3 4 4 2 2 3
これは1つの完全なラウンドロビンになります...次のマッチは...になります
1 2
3 4
プログラムで、これにアプローチする方法がいくつかあります。たぶん、上記のコードは同じことをしますlol ..
これらの制約をブール式としてエンコードし、SATソルバーを使用してソリューションを取得します（たとえば、MiniSAT for C ++、SAT4J for Java、独自のソルバーを作成することもできます）。これらのソルバーへの入力は、DIMACSによって標準化されています。
参照 ＆quot;ソーシャルゴルファー問題のSATエンコーディング＆quot;および「トーナメントスケジュール用のSATベースのスケジューラ」同様の問題のSATエンコード用。
実装のショット
public interface ITeam
{
bool PlaysOn(DateTime date);
bool canPlay(ITeam); //returns true if a game between the teams is legal (played once/twice
//already, same different divisions and other applicable rules
}
IEnumerable<ITeam> teams = null; //replace with initialization
IEnumerable<ITeams> reversed = team.Reverse();
IEnumerable<DateTIme> gameDays = null;//replace with initialization
var count = teams.Count();
foreach(var date in gameDays)
{
for(int i = 0;i<count;i++)
{
var innerTeams = i % 2 == 0 ? teams : reversed;
var team = (from t in innerTeams
where !t.PlaysOn(date)
select t).First();
var opp = (from t in teams
where !t.PlaysOn(date) && t.CanPlay(team)
select t).First();
SetupGame(team,opp);
}
} //lot of optimazation possible :)
私はそれを紙でテストしただけですが、私のセットアップでは機能します。チームリストの先頭から開始することとリストの最後から開始することを交互に繰り返すことにより、同じチームが同じテストを何度も繰り返す（または同じ日に繰り返しプレイする）という状況を回避します。起こり得るすべての出会いを異なる相手として表していますが、それは基本的にCanPlayメソッドが行うべきことです。 完全な解決策ではないにしても、これが役立つことを願っています
