锦标赛分组放置算法

发布于 2024-12-19 07:48:33 字数 456 浏览 3 评论 0原文

给定对手种子列表（例如种子 1 到 16），我正在尝试编写一种算法，该算法将导致头号种子在该轮中对阵最低的种子，第二名种子对阵第二低的种子，依此类推。

将 1 和 16、2 和 15 等分组为“比赛”相当容易，但我还需要确保较高的种子将在后续回合中与较低的种子比赛。

正确排名的括号示例：

如您所见，种子 1 和种子 2 仅在决赛中相遇。

原文

Given a list of opponent seeds (for example seeds 1 to 16), I'm trying to write an algorithm that will result in the top seed playing the lowest seed in that round, the 2nd seed playing the 2nd-lowest seed, etc.

Grouping 1 and 16, 2 and 15, etc. into "matches" is fairly easy, but I also need to make sure that the higher seed will play the lower seed in subsequent rounds.

An example bracket with the correct placement:

As you can see, seed 1 and 2 only meet up in the final.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

未蓝澄海的烟 2024-12-26 07:48:33

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

This JavaScript returns an array where each even index plays the next odd index

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]

回复收藏 0 原文

水波映月 2024-12-26 07:48:33

根据您的假设，选手 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}

如您所见，它生成与您发布的相同的树。

With your assumptions, players 1 and 2 will play in the final, players 1-4 in the semifinals, players 1-8 in the quarterfinals and so on, so you can build the tournament recursively backwards from the final as AakashM proposed. Think of the tournament as a tree whose root is the final.

In the root node, your players are {1, 2}.

To expand the tree recursively to the next level, take all the nodes on the bottom layer in the tree, one by one, and create two children for them each, and place one of the players of the original node to each one of the child nodes created. Then add the next layer of players and map them to the game so that the worst newly added player plays against the best pre-existing player and so on.

Here first rounds of the algorithm:

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

As you can see, it produces the same tree you posted.

回复收藏 0 原文

夢归不見 2024-12-26 07:48:33

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

I've come up with the following algorithm. It may not be super-efficient, but I don't think that it really needs to be. It's written in 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);
    }
?>

回复收藏 0 原文

二智少女猫性小仙女 2024-12-26 07:48:33

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

它执行了 darkangel 的要求：将所有种子返回到正确的位置。比赛与他的示例中的相同，但按照更漂亮的顺序，种子 1 和种子 16 位于架构的外部（正如您在网球锦标赛中看到的那样）。

如果没有出现冷门（意味着较高种子选手总是从较低种子选手手中获胜），您将在决赛中以 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

I also wrote a solution written in PHP. I saw Patrik Bodin's answer, but thought there must be an easier way.

It does what darkangel asked for: It returns all seeds in the correct positions. The matches are the same as in his example, but in a prettier order, seed 1 and seed number 16 are on the outside of the schema (as you see in tennis tournaments).

If there are no upsets (meaning a higher seeded player always wins from a lower seeded player), you will end up with seed 1 vs seed 2 in the final.

It actually does two things more:

It shows the correct order (which is a requirement for putting byes in the correct positions)
It fills in byes in the correct positions (if required)

A perfect explanation about what a single elimination bracket should look like: http://blog.playdriven.com/2011/articles/the-not-so-simple-single-elimination-advantage-seeding/

Code example for 16 participants:

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

?>

The output:

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

If you change 16 into 6 you get:

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

回复收藏 0 原文

梦幻的心爱 2024-12-26 07:48:33

# 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

# 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

回复收藏 0 原文

寒江雪… 2024-12-26 07:48:33

对于 JavaScript 代码，请使用以下两个函数之一。前者体现了命令式风格和命令式风格。速度要快得多。后者是递归的&更整洁，但仅适用于相对较少数量的团队（<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
}

在这里，您可以通过镜像已经占用的位置来一一填充这些位置。例如，一号种子球队（即号码 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)

For JavaScript code, use one of the two functions below. The former embodies imperative style & is much faster. The latter is recursive & neater, but only applicable to relatively small number of teams (<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
}

Here you fill in the spots one by one by mirroring already occupied ones. For example, the first-seeded team (that is number 0) goes to the topmost spot. The second one (1) occupies the opposite spot in the other half of the bracket. The third team (2) mirrors 1 in their half of the bracket & so on. Despite the nested loops, the algorithm has a linear time complexity depending on the number of teams.

Here is the recursive method:

// functional style
const foo = n =>
  n === 1 ? [0] : foo(n >> 1).reduce((p, c) => [...p, c, n - c - 1], [])

Basically, you do the same mirroring as in the previous function, but recursively:

For n = 1 team, it's just [0].
For n = 2 teams, you apply this function to the argument n-1 (that is,
1) & get [0]. Then you double the array by inserting mirrored
elements between them at even positions. Thus, [0] becomes [0, 1].
For n = 4 teams, you do the same operation, so [0, 1] becomes [0, 3, 1, 2].

If you want to get human-readable output, increase each element of the resulting array by one:

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

回复收藏 0 原文

聽兲甴掵 2024-12-26 07:48:33

每轮按种子标准对球队进行排序
（如果一轮中有 n 支球队）第 i 名球队与球队 n-i+1 比赛

回复收藏 0 原文

深陷 2024-12-26 07:48:33

由于在搜索该主题时会出现这种情况，并且不可能找到另一个解决问题的答案并将种子放在“更漂亮”的顺序中，因此我将添加来自 darkangel 的 PHP 代码版本。我还添加了向较高种子选手告别的可能性。

这是在 OO 环境中编码的，因此参与者的数量在 $this->finalists 中，轮空的数量在 $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;
    }

Since this comes up when searching on the subject, and it's hopeless to find another answer that solves the problem AND puts the seeds in a "prettier" order, I will add my version of the PHP code from darkangel. I also added the possibility to give byes to the higher seed players.

This was coded in an OO environment, so the number of participants are in $this->finalists and the number of byes are in $this->byes. I have only tested the code without byes and with two 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;
    }

回复收藏 0 原文

避讳 2024-12-26 07:48:33

我开发了一个 PHP / Laravel 插件，可以生成带/不带初步循环的括号。也许它对你有用，我不知道你用的是什么技术。这是github。

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

希望有帮助！

回复收藏 0 原文

云朵有点甜 2024-12-26 07:48:33

交流版本。

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

A C version.

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

回复收藏 0 原文

情魔剑神 2024-12-26 07:48:33

答案有点取决于其他变量。这是我解决问题的方法。它仅解决创建括号的第一位。括号变小的其他逻辑取决于读者。

您需要知道抽签规模，至少为 8 名
玩家。您至少需要抽签人数的一半，例如 8 名抽签至少有 4 名玩家。
您的玩家群体中有种子选手和非种子选手、通配符或预选赛选手。

将所有玩家组相加，看看玩家数量是否等于抽签大小。如果玩家组人数小于抽签人数，您需要添加“再见”。
如果轮空，您需要将轮空分配给（最高）种子选手。这将导致您的前几场种子比赛（假设您有种子选手）。
a.抽签中，您的种子选手可能少于轮空，但您确实有非种子选手、外卡选手或预选赛选手。这些可以被授予剩余的轮空。我将这些案例视为种子选手。您可以根据自己的意愿将资格赛选手或外卡选手视为种子选手。但我发现一个带有限定符、通配符和轮空的括号很奇怪。
如果您有非种子选手、通配符或预选赛选手，请创建与种子选手的比赛并将其附加到您的种子比赛中。
如果您没有非种子选手、通配符或预选赛选手，您需要将种子选手组分成两半。假设您有 8 个种子，您必须将其分组：1-4、5-8。您需要颠倒第二组的顺序。您现在需要为其余种子创建匹配。种子比赛到此结束。
要创建括号，您必须将种子比赛分成左右两半。左侧有 1 号种子，右侧有 2 号种子，3 号种子进入左侧，4 号种子进入右侧，以此类推。右侧还可以容纳一粒或多粒种子，且不等号。种子数量。除非你只有一颗种子，否则这颗种子会留在左侧。
最好稍微调整一下括号（左右），以确保 1 号种子不会在一轮后的抽签规模为 16 及以上的情况下与 3 号种子比赛。
a.您为括号创建两个数组（foo 和 bar）。
b.当您循环每个括号时，第一个匹配项和最后一个匹配项将进入 foo，第二个和倒数第二个匹配项将进入 bar。
c.如果您希望您的种子选手与最差的种子选手比赛，您必须将括号分成两半，反转两边，然后再次合并。如果您允许种子之间存在或多或少相等的差异，则可以省略此操作。
d.现在您需要反转 bar 并将 bar 合并到 foo 中，这现在已成为您的括号。
您可以与其余非种子选手、通配符和预选赛创建比赛作为非种子比赛。
完成您需要的最后括号，以确定哪一方拥有最少的条目来开始添加第一个非种子比赛。这需要以下逻辑（假设从 0 开始的数组）。
a.在比赛中放置某项内容的索引是 1。根据您所在的球队，您需要将第一场比赛添加为 1 号或 2 号种子的对手。如果数组为空，则将其push到数组中。
b.每第二次迭代，您都会通过将索引乘以 -1 来翻转索引，这意味着在大多数语言中，您将把它添加到数组的最后一个元素之前。
c.为了确保所有种子玩家之间的间距相等，您需要在每第二次迭代时执行以下操作：
- 当索引大于 0 时，将索引更新 2。
- 如果索引大于其中一个括号大小的一半，则将索引重置为 1。

The answer depends a bit on other variables. This is my approach to the problem. It only addresses the first bit of creating the brackets. The other logic of the bracket getting smaller is up to the reader.

You need to know the draw size, with a minimum of 8
You need a minimum of half the draw size in players, eg draw of 8 has a minimum of 4 players.
You have seeded and optionally unseeded, wildcards or qualifiers in your player population.

Add up all the player groups and see if the player count equals the draw size. If the player group size is less than the draw size, you'll need to add "Byes".
In case of Byes, you'll need to assign the Byes to the (highest) seeded player(s). This results in your first couple of seeded matches (assuming you have seeded players).
a. It could be that you have less seeded players than Byes in a draw but you do have unseeded, wildcards or qualifiers. These can be granted the remainding Byes. I treat these cases as seeded players. You can treat qualifiers or wild cards as seeded players depending on your wishes. But I find a bracket with qualifiers, wildcards and byes odd.
If you have unseeded players, wildcards or qualifiers, create matches vs the seeded players and append this to your seeded matches.
If you don't have unseeded players, wildcards or qualifiers you'll need to split your seeded player group in half. Assuming you have 8 seeds, you'll have to groups: 1-4, 5-8. You'll need to reverse the order of the second group. You now need to create matches for the remainder of the seeds. This concludes the seeded matches.
To create the brackets you have to split the seeded matches in half to a left and a right side. The left side has the #1 seed in it, the right side has the #2 seed in it, the #3 seed goes into left and #4 seed into right, etc. The right side also holds one seed or more with an unequal amount of seeds. Unless you only have one seed, this one stays on the left side.
It would be best if you shuffled the brackets (both left and right) a bit to ensure that the no 1 seed doesn't play the no 3 seed one round later in a draw size of 16 and up.
a. You create two arrays (foo and bar) for a bracket.
b. While you loop over each bracket, the first match and last match go into foo and the second and second to last match into bar.
c. If you prefer your seeds to play against the worst seeded players, you must split the bracket in half, reverse both sides, and merge them again. You can omit this action if you allow a more or less equal difference between seeds.
d. Now you need to reverse the bar and merge bar into foo, this has now become your bracket.
You create matches with the remainder of the unseeded players, the wildcards and the qualifiers as unseeded matches.
Complete the final brackets you need to determine which side has the fewest entries to start adding the first unseeded match to. This requires the following logic (assuming 0-based arrays).
a. The index to place something in the matches is 1. Depending on the side you are working on, you'll want to add the first match as the opponent of the #1 or #2 seed. If the array is empty, just push it to the array.
b. Every second interation you flip the index by multiplying it with -1, this means in most languages that you'll add it before the last element of the array.
c. To make sure you have equal spacing between all the seeded players you'll need to do the following things at every second iteration:
- Update the index by 2 when the index is more than 0.
- Reset the index to 1 if the index is greater than half the size of one of the brackets.

回复收藏 0 原文

╰ゝ天使的微笑 2024-12-26 07:48:33

老问题，但我在研究这个问题时遇到了它。基于 AakashM 和 Antti Huima 的通用算法，这是我在 C# 中最终得到的结果。我确信它不是计算效率最高的，但我编写它是为了易于理解（对我自己而言）并且易于移植

除了创建括号之外，它还设置了一个 Round 值和一个 种子值，为了使排序更容易，我需要将种子作为显式值存储在数据库中，而不必依赖 id 顺序。参与者应该按等级排序，但并非必须如此。如果参赛人数不是二的倍数，则会产生轮空组（多余的球队没有对手）。

要创建固定规模的锦标赛（例如少于 32 名玩家的 64 组锦标赛），您可以让主 while 循环运行更长的时间，这将创建额外的空括号。

希望有人觉得这有帮助！

var participants = Enumerable.Range(1, 64).Select(s => (long)s).ToList();
var brackets = GenerateBrackets(participants);

static List<Bracket> GenerateBrackets(List<long> participants)
{
    var totalRounds = 1;
    int participantIndex = 0;
    var finalBracket = new Bracket
    {
        Red = participants.ElementAtOrDefault(participantIndex++),
        Blue = participants.ElementAtOrDefault(participantIndex++),
    };
    var currentRound = new List<Bracket>();
    var previousRound = new List<Bracket> { finalBracket };

    while (participantIndex < participants.Count)
    {
        totalRounds++;
        currentRound.Clear();

        foreach (var bracket in previousRound)
        {
            bracket.RedParentBracket = new Bracket
            {
                ChildBracket = bracket,
                Red = bracket.Red
            };

            bracket.BlueParentBracket = new Bracket
            {
                ChildBracket = bracket,
                Red = bracket.Blue
            };

            currentRound.Add(bracket.RedParentBracket);
            currentRound.Add(bracket.BlueParentBracket);
        }

        foreach (var newBracket in currentRound.OrderByDescending(b => participants.IndexOf(b.Red)))
            newBracket.Blue = participants.ElementAtOrDefault(participantIndex++);

        previousRound.Clear();
        previousRound.AddRange(currentRound);
    }

    finalBracket.Round = totalRounds;
    SetDepthOnParents(finalBracket);

    var orderedBrackets = new List<Bracket>();
    for (var i = 1; i <= finalBracket.Round; i++)
        OrderBracketsInRoundBySeed(finalBracket, i, orderedBrackets);

    for (int i = 0; i < orderedBrackets.Count; i++)
        orderedBrackets[i].Seed = i + 1;

    return orderedBrackets;
}

static void OrderBracketsInRoundBySeed(Bracket bracket, int round, List<Bracket> brackets)
{
    if (bracket == null)
        return;
    else if (bracket.Round == round)
        brackets.Add(bracket);
    else
    {
        OrderBracketsInRoundBySeed(bracket.RedParentBracket, round, brackets);
        OrderBracketsInRoundBySeed(bracket.BlueParentBracket, round, brackets);
    }
}

static void SetDepthOnParents(Bracket bracket)
{
    if (bracket == null)
        return;

    if (bracket.RedParentBracket != null)
    {
        bracket.RedParentBracket.Round = bracket.Round - 1;
        SetDepthOnParents(bracket.RedParentBracket);
    }
    if (bracket.BlueParentBracket != null)
    {
        bracket.BlueParentBracket.Round = bracket.Round - 1;
        SetDepthOnParents(bracket.BlueParentBracket);
    }
}

public class Bracket
{
    public long Red { get; set; }
    public long Blue { get; set; }
    public int Round { get; set; }
    public int Seed { get; set; }

    public Bracket ChildBracket { get; set; }
    public Bracket RedParentBracket { get; set; }
    public Bracket BlueParentBracket { get; set; }
}

Old issue but i ran across it while researching this problem. Based on the general algorithm from AakashM and Antti Huima, here is what i ended up with in c#. I'm sure its not the most computationally effective but i wrote it to be easy to follow (for my self) and easily portable

Besides creating the brackets, it also sets a Round value and a Seed value, to make sorting easier, i needed the seed as an explicit value to store in the database and not have to rely on id order. Participants are expected to be sorted by rank but they dont have to be. If the number of participants is not a multiple of two it will create bye brackets (where excess teams have no opponent).

To create a tournament of a fixed size like a 64 bracket tournament with less than 32 players you can just let the main while loop run longer, this will create additional empty brackets.

Hopefully someone finds this helpful!

var participants = Enumerable.Range(1, 64).Select(s => (long)s).ToList();
var brackets = GenerateBrackets(participants);

static List<Bracket> GenerateBrackets(List<long> participants)
{
    var totalRounds = 1;
    int participantIndex = 0;
    var finalBracket = new Bracket
    {
        Red = participants.ElementAtOrDefault(participantIndex++),
        Blue = participants.ElementAtOrDefault(participantIndex++),
    };
    var currentRound = new List<Bracket>();
    var previousRound = new List<Bracket> { finalBracket };

    while (participantIndex < participants.Count)
    {
        totalRounds++;
        currentRound.Clear();

        foreach (var bracket in previousRound)
        {
            bracket.RedParentBracket = new Bracket
            {
                ChildBracket = bracket,
                Red = bracket.Red
            };

            bracket.BlueParentBracket = new Bracket
            {
                ChildBracket = bracket,
                Red = bracket.Blue
            };

            currentRound.Add(bracket.RedParentBracket);
            currentRound.Add(bracket.BlueParentBracket);
        }

        foreach (var newBracket in currentRound.OrderByDescending(b => participants.IndexOf(b.Red)))
            newBracket.Blue = participants.ElementAtOrDefault(participantIndex++);

        previousRound.Clear();
        previousRound.AddRange(currentRound);
    }

    finalBracket.Round = totalRounds;
    SetDepthOnParents(finalBracket);

    var orderedBrackets = new List<Bracket>();
    for (var i = 1; i <= finalBracket.Round; i++)
        OrderBracketsInRoundBySeed(finalBracket, i, orderedBrackets);

    for (int i = 0; i < orderedBrackets.Count; i++)
        orderedBrackets[i].Seed = i + 1;

    return orderedBrackets;
}

static void OrderBracketsInRoundBySeed(Bracket bracket, int round, List<Bracket> brackets)
{
    if (bracket == null)
        return;
    else if (bracket.Round == round)
        brackets.Add(bracket);
    else
    {
        OrderBracketsInRoundBySeed(bracket.RedParentBracket, round, brackets);
        OrderBracketsInRoundBySeed(bracket.BlueParentBracket, round, brackets);
    }
}

static void SetDepthOnParents(Bracket bracket)
{
    if (bracket == null)
        return;

    if (bracket.RedParentBracket != null)
    {
        bracket.RedParentBracket.Round = bracket.Round - 1;
        SetDepthOnParents(bracket.RedParentBracket);
    }
    if (bracket.BlueParentBracket != null)
    {
        bracket.BlueParentBracket.Round = bracket.Round - 1;
        SetDepthOnParents(bracket.BlueParentBracket);
    }
}

public class Bracket
{
    public long Red { get; set; }
    public long Blue { get; set; }
    public int Round { get; set; }
    public int Seed { get; set; }

    public Bracket ChildBracket { get; set; }
    public Bracket RedParentBracket { get; set; }
    public Bracket BlueParentBracket { get; set; }
}

回复收藏 0 原文

~没有更多了~