質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.50%

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

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 3,058

score 39

前提・実現したいこと

トーナメント表をswiftで作りたいです。
イメージ説明
8・16・32...とシードがない状況のトーナメントの作成は出来ましたが、
シードがあるトーナメント表が作れません。

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

試したこと

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

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

知りたい事

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

追記

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

追記2

イメージ説明

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+3

シードが発生する条件は、参加チーム数が 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 から削る、というように均等に割り振らねばなりませんが。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/09/02 16:52

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

    キャンセル

  • 2019/09/02 17:17

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

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

    キャンセル

  • 2019/09/02 21:12

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

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

    キャンセル

  • 2019/09/04 02:28

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

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.50%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る