比赛支架放置算法

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

此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 2

根据你的假设,球员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 3

我想出了以下算法。它可能不是超级高效，但我认为它确实不是必须的。它是用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);
    }
?>

Answer 4

我还写了一个用 PHP 编写的解决方案。我看到帕特里克·博丁的回答，但认为一定有一个更简单的方法。

它执行了 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