質問: ### 前提・実現したいこと トーナメント表をswiftで作りたいです。 ![イメージ説明](https://teratail-v2.storage.googleapis.com/uploads/contributed_images/7a0fc18eccbdbe756ba905817eb183b4.png) 8・16・32...とシードがない状況のトーナメントの作成は出来ましたが、 シードがあるトーナメント表が作れません。 トーナメントのシードになる場所は上から順番ではなく、上の次は下、真ん中と一定の規則に乗っ取っりながら複雑に増えて行くため、その法則を見つけるのとそれをプログラミングするのが分かりません。 ### 試したこと 色々シードがどのように作られるか調べていましたが、いまいち掴めません。 ![イメージ説明](https://teratail-v2.storage.googleapis.com/uploads/contributed_images/01d77cbd47820677b75722c61a7048dc.png) ![イメージ説明](https://teratail-v2.storage.googleapis.com/uploads/contributed_images/5e11f619d71126f1441217a6156c2b9c.jpeg) 左側が人数で、その人数の時に右側のようにシードの線が引かれるのですが、まだ数式に起こしたりプログラミング出来てないです。 ### 知りたい事 トーナメントの仕組み(アルゴリズム)を理解してコードを書きたいので、トーナメントのアルゴリズムをご教授お願いします。 ### 追記 ![イメージ説明](https://teratail-v2.storage.googleapis.com/uploads/contributed_images/6646b5c5eced51120b7c430d636feef2.png) 11チームの場合次のシードは4か5ってどのように決めるのでしょうか? ![イメージ説明](https://teratail-v2.storage.googleapis.com/uploads/contributed_images/9f9491ee5c660bad5a655851c3b3e21f.png) ![イメージ説明](https://teratail-v2.storage.googleapis.com/uploads/contributed_images/7465f58ef168605d18efd849d166240e.png) ### 追記2 ![イメージ説明](https://teratail-v2.storage.googleapis.com/uploads/contributed_images/f9447379b86a155b80c90d19258eb656.png)
回答: シードが発生する条件は、参加チーム数が 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 の両方を削ればいいことが分かります。 ではさらにもう1チーム減らすには? 今は 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 から削る、というように均等に割り振らねばなりませんが。