比赛支架放置算法

Question

给定一个对手种子列表（例如种子1到16），我试图编写一个算法，这将导致顶部种子播放该轮中最低的种子，第二个种子播放第二最低种子等

将1和16,2和15等分组为“匹配”相当容易，但我还需要确保较高的种子将在随后的回合中播放较低的种子。

一个例子托架与正确放置：

1 vs 16 
      1 vs 8 
8 vs 9 
         1 vs 4 
4 vs 13 
      4 vs 5 
5 vs 12 
            1 vs 2 
2 vs 15 
      2 vs 7 
7 vs 10 
         2 vs 3 
3 vs 14 
      3 vs 6 
6 vs 11

正如你可以看到，种子1和2仅在最后的会面。

Answer 1

我想出了以下算法。它可能不是超高效的，但我认为它不是真的需要。它是用PHP编写的。

<?php 
    $players = range(1, 32); 
    $count = count($players); 

    // Order players. 
    for ($i = 0; $i < log($count/2, 2); $i++) { 
     $out = array(); 

     foreach ($players as $player) { 
      $splice = pow(2, $i); 

      $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); 
    } 
?> 

Answer 2

• 在每轮排序队由播种条件
• （如果有n个圆队）在第i个位置的团队与团队的N-1 + 1

Answer 3

随着你的假设中，玩家扮演1和2将在决赛中进行，半决赛中的球员1-4，四分之一决赛中的球员1-8等等，所以你可以按照AakashM的建议递归地从决赛中退出比赛。把锦标赛想象成一棵树，其根源是决赛。

在根节点中，你的玩家是{1,2}。

要递归地将树扩展到下一层，请逐个树中的底层的所有节点，并为它们各创建两个子节点，并将原节点的其中一个播放器分别放置到每个节点创建的一个子节点。然后添加下一层玩家并将它们映射到游戏中，以便最坏的新添加的玩家与最好的现有玩家对战，等等。

这里第一回合的算法：

{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} 

正如你所看到的，它产生您发布的同一棵树。

Answer 4

这个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] 

Answer 5

# 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 

Answer 6

因为这对主题进行搜索时出现的数组，这是无望找到另一个答案，解决问题，并把种子放在一个“漂亮”的顺序，我会从darkangel添加我的PHP代码版本。我还增加了给予更高的种子选手的可能性。

这是在面向对象的环境下编码的，所以参与者的数量在$ this->入围者中，并且byes的数量在$ this-> 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; 
    } 

Answer 7

对于JavaScript代码，请使用以下两个函数之一。前者体现势在必行的风格&要快得多。后者是递归的&整理者，但只适用于相对较少数量的团队（< 16384）。

在这里你通过镜像已经占用的一个一个地填写点。例如，一号种子团队（编号为0）走到最高点。第二个（1）在括号的另一半占据相反的位置。第三队（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）&得到[0]。然后，通过在它们之间插入镜像的 元素，在偶数位置上加倍阵列。因此，[0]变成[0, 1]。

• 对于n = 4团队，您做同样的操作，所以[0, 1]成为[0, 3, 1, 2]。

如果你想获得人类可读的输出，由一个增加导致数组的每个元素：

const readableArr = arr.map(i => i + 1) 

Answer 8

我也写PHP编写的解决方案。我看到了Patrik Bodin的回答，但认为必须有一个更简单的方法。

它做什么darkangel要求：它返回所有种子在正确的位置。这些比赛与他的例子相同，但在漂亮的顺序中，种子1和种子数量16位于模式的外部（如您在网球锦标赛中看到的那样）。

如果没有失败（意味着更高的种子选手总是从更低的种子选手获胜），那么最终的种子1和种子2将会结束。

它实际上做了两件事更多：

1. 它显示了正确的顺序（这是将轮空在正确位置的要求）

2. 它填补了在正确的位置轮空（如果需要的话）

约一个消除支架应该是什么样一个完美的解释：http://blog.playdriven.com/2011/articles/the-not-so-simple-single-elimination-advantage-seeding/

代码示例16名学员：

<?php 

define('NUMBER_OF_PARTICIPANTS', 16); 

$participants = range(1,NUMBER_OF_PARTICIPANTS); 
$bracket = getBracket($participants); 
var_dump($bracket); 

function getBracket($participants) 
{ 
    $participantsCount = count($participants); 
    $rounds = ceil(log($participantsCount)/log(2)); 
    $bracketSize = pow(2, $rounds); 
    $requiredByes = $bracketSize - $participantsCount; 

    echo sprintf('Number of participants: %d<br/>%s', $participantsCount, PHP_EOL); 
    echo sprintf('Number of rounds: %d<br/>%s', $rounds, PHP_EOL); 
    echo sprintf('Bracket size: %d<br/>%s', $bracketSize, PHP_EOL); 
    echo sprintf('Required number of byes: %d<br/>%s', $requiredByes, PHP_EOL);  

    if($participantsCount < 2) 
    { 
     return array(); 
    } 

    $matches = array(array(1,2)); 

    for($round=1; $round < $rounds; $round++) 
    { 
     $roundMatches = array(); 
     $sum = pow(2, $round + 1) + 1; 
     foreach($matches as $match) 
     { 
      $home = changeIntoBye($match[0], $participantsCount); 
      $away = changeIntoBye($sum - $match[0], $participantsCount); 
      $roundMatches[] = array($home, $away); 
      $home = changeIntoBye($sum - $match[1], $participantsCount); 
      $away = changeIntoBye($match[1], $participantsCount); 
      $roundMatches[] = array($home, $away); 
     } 
     $matches = $roundMatches; 
    } 

    return $matches; 

} 

function changeIntoBye($seed, $participantsCount) 
{ 
    //return $seed <= $participantsCount ? $seed : sprintf('%d (= bye)', $seed); 
    return $seed <= $participantsCount ? $seed : null; 
} 

?> 

输出：

Number of participants: 16 
Number of rounds: 4 
Bracket size: 16 
Required number of byes: 0 
C:\projects\draw\draw.php:7: 
array (size=8) 
    0 => 
    array (size=2) 
     0 => int 1 
     1 => int 16 
    1 => 
    array (size=2) 
     0 => int 9 
     1 => int 8 
    2 => 
    array (size=2) 
     0 => int 5 
     1 => int 12 
    3 => 
    array (size=2) 
     0 => int 13 
     1 => int 4 
    4 => 
    array (size=2) 
     0 => int 3 
     1 => int 14 
    5 => 
    array (size=2) 
     0 => int 11 
     1 => int 6 
    6 => 
    array (size=2) 
     0 => int 7 
     1 => int 10 
    7 => 
    array (size=2) 
     0 => int 15 
     1 => int 2 

如果你改变16进6中，您可以：

Number of participants: 6 
Number of rounds: 3 
Bracket size: 8 
Required number of byes: 2 
C:\projects\draw\draw.php:7: 
array (size=4) 
    0 => 
    array (size=2) 
     0 => int 1 
     1 => null 
    1 => 
    array (size=2) 
     0 => int 5 
     1 => int 4 
    2 => 
    array (size=2) 
     0 => int 3 
     1 => int 6 
    3 => 
    array (size=2) 
     0 => null 
     1 => int 2 

Answer 9

我曾在一个PHP/Laravel生成括号的插件，无论是否进行初步循环。也许它对你有用，我不知道你使用的是什么技术。这是github。

https://github.com/xoco70/kendo-tournaments

希望它能帮助！

Answer 10

C版本。

int * pctournamentSeedArray(int PlayerCnt) 
{ 
    int * Array; 
    int * PrevArray; 
    int i; 

    Array = meAlloc(sizeof(int) * PlayerCnt); 

    if (PlayerCnt == 2) 
    { 
     Array[0] = 0; 
     Array[1] = 1; 
     return Array; 
    } 

    PrevArray = pctournamentSeedArray(PlayerCnt/2); 
    for (i = 0; i < PlayerCnt;i += 2) 
    { 
     Array[i] = PrevArray[i/2]; 
     Array[i + 1] = (PlayerCnt - 1) - Array[i] ; 
    } 
    meFree(PrevArray); 
    return Array; 
}