トーナメント表のアルゴリズム

Question

前提・実現したいこと

トーナメント表をswiftで作りたいです。

8・16・32...とシードがない状況のトーナメントの作成は出来ましたが、
シードがあるトーナメント表が作れません。

トーナメントのシードになる場所は上から順番ではなく、上の次は下、真ん中と一定の規則に乗っ取っりながら複雑に増えて行くため、その法則を見つけるのとそれをプログラミングするのが分かりません。

試したこと

色々シードがどのように作られるか調べていましたが、いまいち掴めません。

左側が人数で、その人数の時に右側のようにシードの線が引かれるのですが、まだ数式に起こしたりプログラミング出来てないです。

知りたい事

トーナメントの仕組み（アルゴリズム)を理解してコードを書きたいので、トーナメントのアルゴリズムをご教授お願いします。

追記

11チームの場合次のシードは4か5ってどのように決めるのでしょうか?

追記2

Answer 1

シードが発生する条件は、参加チーム数が 2^n になっていない場合です。
そして参加チーム数が m のとき、シード数は ** m 以上で、最小の 2^n の値 - m ** となります。
※m = 2^n のときは上記式からシード数が 0 になります
ここで n は決勝を含む、勝ち上がるための試合数になります。
13チームのトーナメントを組む場合、n = 4（2^4 = 16 > 13 > 2^3=8) となり、1回戦（13→8）→2回戦（8→4）→準決勝（4→2）→決勝（2→1）となります。

シード数が決定すれば、あとはトーナメント上でシードになる試合を決めて、その試合の一方の相手を「シードなので不戦敗になる」ことが分かっているように表現すればいいのです。

次に、シードの場所の決定ですが、まず「なるべく不公平にしない」ことがもとめられます。つまり、トーナメントの両翼の片方によるようになっていてはいけないし、決勝までの勝負数が極端に少なくなってもいけません。
ですから一番上がシードになったら、次は一番下がシードになります。
ではその次は、というと、トーナメントの両翼に均等に割り振るので、上側半分の中で、もっとも下にある試合（つまり真ん中に見える）をシードにし、次は下側半分の中で、もっとも上にある試合……という格好になります。

13チームで考えると、まず1回戦目は
A B C D E F G H I J K L M N O P
の16チーム（うち3チームをなくしてシードとする）ですので、A と P を削って、B と O がシードになります。
あと一つはこの16チームの上側（左側）半分、すなわち
a B C D E F G H
の中から（すでにシードで消えているAをaと表現します）もう一つ消すことになるので、反対側の「H」を消します。
さらにこれが12チームでだとすれば、さらにもう1個消すのはトーナメント表の下側（右側）半分から、
I J K L M N O p
P と I の両方を削ればいいことが分かります。

ではさらにもう１チーム減らすには？　今は
a B C D E F G h i J K L M N O p
となっていますが、半分は使い切りましたから、さらにその半分、つまり
a B C D
に着目して、ここから D を削るのです。
要するに、半分ずつにしてその端を除外する、をくり返していけばいいはずです。
※ただし5個以上シードとする場合、ABCD, EFGH, IJKL, MNOPの中から ABCD で削ったら、次は MNOP から削る、というように均等に割り振らねばなりませんが。

Comments

[toto654]

回答の通りやって行くとこれどっちが先かって問題が度々出て来ることに気が付きました。その一例を上記に追記として追加させて頂きました。　
13チームの場合などチーム数が少ないと感覚で分かりますが、チーム数が増えて来ると次はどこにシードが来るのか分からなくなってきてしまいます。

[tacsheaven]

全チームを1回戦の場所に（シードで消える分も含めて）配置した状態を考えます。
ここから、シード数が2までなら、1回戦の全体を1つのブロックとしてみて、その両端を消します。
次にシード数が4までなら、上に加えて「前の処理でみたブロックを各々二つに分割して」それぞれのブロックの両端を消します。
次にシード数が8までなら、上に加えて「前の処理で見たブロックを各々二つに分割して」それぞれの両端を消します。ただしブロック（都合四つ）のうち、処理の順序は「先頭」→「末尾」→「2番目」→「3番目」の順になります。これは四つのブロックをリストとして並べたときに、「リストの先頭のブロックを処理して、そのブロックをリストから除く」→「リストの末尾のブロックを処理して、そのブロックをリストから除く」→をくり返せばよいですね。

こうやって見ると、繰り返しがあることに気づきませんか？

[toto654]

偶数個のシードの場合、両端を消して行くため分かりやすいですが、奇数個のシードだった場合にどうしても分かりません。。　追記にあるような場合は4か5かどちらが先だと判断できますか？

また、追記2にも追加させて頂きましたが、シードが現在8ある状況で次のシードがどこに出来るかはどのように分かりますか？

[tacsheaven]

奇数個の場合は消す対象が減るだけです。シード数が1の時は、全体の先頭だけ消して最後は消しませんでしたよね？　それと同じ事です。
シード数による削り方ですが、
シード数が 2 以下（= 2^1）なら、全体を1（※ 2^(1-1)）ブロックとして両端を消す。
シード数が 4 以下（= 2^2）なら、上に加えて全体を2（※ 2^(2-1))ブロックに分割してそれぞれの両端を消す
シード数が 8 以下（= 2^3）なら、上に加えて全体を4（※ 2^(3-1))ブロックに分割してそれぞれの両端を消す

……はい、繰り返しが見えてきませんか？