読者です 読者をやめる 読者になる 読者になる

意外と簡単!1vs1の総当りリーグ戦のスケジュール

この記事はNCC Advent Calendar 2015の23日目の記事です。

昨日はtkdくんによる"あなたの知らないSurfaceの闇"でした。

前回、私が書いた記事はなんか堅苦しい感じになってしまったので、今回はゆるふわな感じでいきたいと思います。

ちなみに、NCC Advent Calendar 2015も残すところあと2日ですが、この記事は例によって技術的な話はまったくないです。(スンマセン

今回は、1vs1の総当りリーグ戦のスケジュールを組むアルゴリズムについて話そうと思います。

 

Chapter 1. 1vs1の総当りリーグ戦とは

1vs1の総当りリーグ戦とは野球やサッカーなどの1対1で試合をする競技の総当りリーグ戦のことを指します。日本のプロ野球Jリーグもこの総当りリーグ戦が行われています。

わかりやすくJリーグの例で説明しましょう。
J1リーグの試合は、すべてのチーム対が2回ずつ試合を行う二重総当り戦になっています。現在J1には18チームが所属していますので、各チームは自分以外の17チームと2回ずつ、2×17=34節からなるスケジュールを戦います。

例として、18チームのスケジュールをすべて書くのは大変なので、6チームのスケジュールを下の表1に示します。

表1. チーム数6のスケジュール

f:id:Korokorotune:20151222163339p:plain

 表1をよく見ると、全チーム毎節どこか別のチームと試合をしており、なおかつ5節ですべての他チームと試合を行っています。

実はこのスケジュール、適当に組んでもできるわけではないのです。やってみればわかりますが、適当にスケジュールを組んでいくと、最後の方の節で残りの試合が収まらないことがあります。

全6チームでもこの有様なので、J1リーグのような全18チームのスケジューリングは当然アルゴリズムを考える必要があります。

 

Chapter 2. アルゴリズム

 実は上記のような問題はチーム数が偶数ならばスケジュールが絶対に作れることをKirkmanという数学者が1847年に証明(スケジュールの存在性)しています。

ですが、この記事でその証明のことを解説しても「?」なことになりかねないので、スケジュールを組むためのアルゴリズムだけ説明します。これが意外と簡単なんです!

 Kirkmanが証明したスケジュールの存在性とは以下の図1のような円盤をまわして、試合の組み合わせを決めるアルゴリズムです。

f:id:Korokorotune:20151223013034p:plain

図1 スケジュールの存在性1

以下の表2は図1のスケジュールを表にしたものです。

表2 スケジュールの存在性1

f:id:Korokorotune:20151223013057p:plain

図1をみておわかりいただけたでしょうか?
このように試合の組み合わせを示す棒を円にそって回していくと、表2のような綺麗なスケジュールが出来上がります。

これ、すごくないですか?初めて知った時、感動しました。

ちなみにこのアルゴリズムでは、組み合わせだけでなく、試合のホーム&アウェー(スポーツ)や先手後手(将棋等)も決めることができます。

f:id:Korokorotune:20151223014257p:plain

図2 スケジュールの存在性2

以下の表3は図2のスケジュールを表にしたものです。

表3 スケジュールの存在性2(対戦相手が青字の時はホームゲーム)

f:id:Korokorotune:20151223014413p:plain

先ほどの図1とは違い、図2には矢印がついています。
(始点)→(終点)とすると、始点はアウェーゲーム(後手)、終点はホームゲーム(先手)とします。このように定義し、円盤をまわすごとに矢印の向きを変えていくと、表3のようにホームアウェーがいい感じで各チームにばらけます。

 すごい。ちょーすごい。感動。

 

 

というようなことを10月頃にmyst研で調べていて、一人で盛り上がっていました^^;