対戦相手のシード (たとえば、シード 1 から 16) のリストが与えられた場合、そのラウンドで最上位のシードが最も低いシードをプレイし、2 番目のシードが 2 番目に低いシードをプレイするなどのアルゴリズムを作成しようとしています。
1 と 16、2 と 15 などを "マッチ" にグループ化するのはかなり簡単ですが、次のラウンドで上位のシードが下位のシードと対戦するようにする必要もあります。
正しい配置のブラケットの例:
1対16
1対8
8対9
1対4
4 対 13
4対5
5 対 12
1対2
2対15
2対7
7 対 10
2対3
3 対 14
3対6
6対11
ご覧のとおり、シード 1 と 2 は決勝戦でのみ対戦します。
この JavaScript は、各偶数インデックスが次の奇数インデックスを再生する配列を返します
function seeding(numPlayers){
var rounds = Math.log(numPlayers)/Math.log(2)-1;
var pls = [1,2];
for(var i=0;i<rounds;i++){
pls = nextLayer(pls);
}
return pls;
function nextLayer(pls){
var out=[];
var length = pls.length*2+1;
pls.forEach(function(d){
out.push(d);
out.push(length-d);
});
return out;
}
}
> seeding(2)
[1, 2]
> seeding(4)
[1, 4, 2, 3]
> seeding(8)
[1, 8, 4, 5, 2, 7, 3, 6]
> seeding(16)
[1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11]
あなたの仮定では、プレーヤー 1 と 2 が決勝でプレーし、プレーヤー 1 ～ 4 が準決勝で、プレーヤー 1 ～ 8 が準々決勝などでプレーするため、AakashM が提案したように、決勝から逆方向に再帰的にトーナメントを構築できます。トーナメントを、決勝を根とする木と考えてください。
ルート ノードでは、プレイヤーは {1, 2} です。
ツリーを再帰的に次のレベルに展開するには、ツリーの最下層にあるすべてのノードを 1 つずつ取得し、それぞれに 2 つの子を作成し、元のノードのプレーヤーの 1 人を子のそれぞれに配置します。ノードが作成されました。次に、プレーヤーの次のレイヤーを追加し、それらをゲームにマッピングして、新しく追加された最悪のプレーヤーが既存の最良のプレーヤーと対戦するようにします。
アルゴリズムの最初のラウンドは次のとおりです。
{1,2} --- create next layer
{1, _}
/ --- now fill the empty slots
{1,2}
\{2, _}
{1, 4} --- the slots filled in reverse order
/
{1,2}
\{2, 3} --- create next layer again
/{1, _}
{1, 4}
/ \{4, _}
{1,2} --- again fill
\ /{2, _}
{2, 3}
\{3, _}
/{1, 8}
{1, 4}
/ \{4, 5} --- ... and so on
{1,2}
\ /{2, 7}
{2, 3}
\{3, 6}
ご覧のとおり、投稿したのと同じツリーが生成されます。
私は次のアルゴリズムを思いついた。それほど効率的ではないかもしれませんが、実際にそうする必要はないと思います。PHPで書かれています。
<?php
$players = range(1, 32);
$count = count($players);
$numberOfRounds = log($count / 2, 2);
// Order players.
for ($i = 0; $i < $numberOfRounds; $i++) {
$out = array();
$splice = pow(2, $i);
while (count($players) > 0) {
$out = array_merge($out, array_splice($players, 0, $splice));
$out = array_merge($out, array_splice($players, -$splice));
}
$players = $out;
}
// Print match list.
for ($i = 0; $i < $count; $i++) {
printf('%s vs %s<br />%s', $players[$i], $players[++$i], PHP_EOL);
}
?>
# Here's one in python - it uses nested list comprehension to be succinct:
from math import log, ceil
def seed( n ):
""" returns list of n in standard tournament seed order
Note that n need not be a power of 2 - 'byes' are returned as zero
"""
ol = [1]
for i in range( ceil( log(n) / log(2) ) ):
l = 2*len(ol) + 1
ol = [e if e <= n else 0 for s in [[el, l-el] for el in ol] for e in s]
return ol
JavaScript コードの場合、以下の 2 つの関数のいずれかを使用します。前者は命令型スタイルを具現化しており、はるかに高速です。後者は再帰的でより簡潔ですが、比較的少数のチーム (<16384) にのみ適用されます。
// imperative style
function foo(n) {
const arr = new Array(n)
arr[0] = 0
for (let i = n >> 1, m = 1; i >= 1; i >>= 1, m = (m << 1) + 1) {
for (let j = n - i; j > 0; j -= i) {
arr[j] = m - arr[j -= i]
}
}
return arr
}
ここでは、すでに占有されているスポットをミラーリングして、スポットを 1 つずつ埋めます。たとえば、最初にシードされたチーム ( number 0) が最上位になります。2 番目のもの ( 1) は、ブラケットの残りの半分の反対側の場所を占めています。3 番目のチーム ( 2)1はブラケットの半分をミラーリングします。ネストされたループにもかかわらず、アルゴリズムはチームの数に応じて線形の時間の複雑さを持ちます。
再帰的な方法は次のとおりです。
// functional style
const foo = n =>
n === 1 ? [0] : foo(n >> 1).reduce((p, c) => [...p, c, n - c - 1], [])
基本的に、前の関数と同じミラーリングを行いますが、再帰的に:
n = 1チームの場合は、[0].
チームの場合n = 2、この関数を引数n-1(つまり
1) & getに適用します[0]。次に、それらの間にミラー化された要素を偶数位置に挿入して、配列を 2 倍にします。したがって、 に[0]なり[0, 1]ます。
n = 4チームの場合、同じ操作を行うため、 になり[0, 1]ます[0, 3,
1, 2]。
人間が読める出力を取得したい場合は、結果の配列の各要素を 1 ずつ増やします。
const readableArr = arr.map(i => i + 1)
件名を検索するとこれが表示され、問題を解決し、シードを「きれいな」順序にする別の回答を見つけることは絶望的であるため、darkangel から私のバージョンの PHP コードを追加します。また、より上位のシード プレイヤーに不戦勝を与える可能性も追加しました。
これは OO 環境でコーディングされているため、参加者の数は $this->finalists にあり、不戦勝の数は $this->byes にあります。Byes なしと 2 Byes ありのコードのみをテストしました。
public function getBracket() {
$players = range(1, $this->finalists);
for ($i = 0; $i < log($this->finalists / 2, 2); $i++) {
$out = array();
$reverse = false;
foreach ($players as $player) {
$splice = pow(2, $i);
if ($reverse) {
$out = array_merge($out, array_splice($players, -$splice));
$out = array_merge($out, array_splice($players, 0, $splice));
$reverse = false;
} else {
$out = array_merge($out, array_splice($players, 0, $splice));
$out = array_merge($out, array_splice($players, -$splice));
$reverse = true;
}
}
$players = $out;
}
if ($this->byes) {
for ($i = 0; $i < $this->byes; $i++ ) {
for ($j = (($this->finalists / pow(2, $i)) - 1); $j > 0; $j--) {
$newPlace = ($this->finalists / pow(2, $i)) - 1;
if ($players[$j] > ($this->finalists / (pow(2 ,($i + 1))))) {
$player = $players[$j];
unset($players[$j]);
array_splice($players, $newPlace, 0, $player);
}
}
}
for ($i = 0; $i < $this->finalists / (pow(2, $this->byes)); $i++ ) {
$swap[] = $players[$i];
}
for ($i = 0; $i < $this->finalists /(pow(2, $this->byes)); $i++ ) {
$players[$i] = $swap[count($swap) - 1 - $i];
}
return array_reverse($players);
}
return $players;
}