分选竞赛种子

Question

我正在制作一个HTML/JS支持的单/双消除支架网络应用程序。我很难从种子队/球员名单中找到如何分配第一轮比赛的方法。例如，在由8人组成的队伍中，第一轮比赛如下：

1v8 4v5 2v7 3v6

在更一般的术语中，种子可以被认为是一个数组(我通过将它们从数组上弹出来分配球队参加比赛)：1,2,3,4,5,6,7,8

需要分类如下: 1,8,4,5,2,7,3,6

为了澄清的是，在排序数组中，较高的种子需要有最大的距离，这样，在没有混乱的括号中，先敲掉较低的种子，并尽可能晚地与高种子匹配。在实际情况下，想想网球锦标赛，你想要阻止16或32岁的前四名选手在半决赛前互相比赛。因此，16个种子括号的正确数组输出是：

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

以下是第一轮比赛：

1v16 8v9 4v13 5v12 2v15 7v10 3v14 6v11

感谢Matt Ball为8种子托架的正确算法

Answer 1

我已经想出了一个解决方案，但它超出了“排序数组”的范围。

(javascript)代码位于http://jsbin.com/ukomo5/2/edit。

在基本条件下，该算法假设括号内不会出现任何颠簸，因此种子1和种子2应该在最后一轮中相遇。它在每一轮中迭代每个种子(从预先计算的总决赛开始，向后工作)，在上一轮的比赛中计算当前种子(在迭代中)获胜的未知种子。这是可以做到的，因为给定一个种子和整数，您可以计算出其他种子应该是什么：

其他种子=圆形+1中的种子数-已知种子

为了说明，在半决赛中：

半决赛1(已知种子为1)：其他种子=4+1-1=4

半决赛2(已知种子为2)：其他种子=4+1-2=3

我只是注意到这个模式时，我看到了“没有不安”的括号，我已经画。

在最后的迭代(即第1轮)中，所有种子及其位置都是已知的，准备分配给匹配。正确的排序数组如下：

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

再次感谢Matt，他为小括号提出了一个正确的解决方案(在没有详细上下文的情况下，很难说明问题和想要的解决方案，而我在最初的问题中并没有完全做到这一点)。

如果有人有其他的解决方案或更优雅的版本我的解决方案，让我们知道！

Answer 2

从上到下匹配玩家的想法是正确的，但并不完全。在第一轮的比赛中，这样做是非常有效的：

while (seeds.length)
{
    firstRound.push(seeds.shift());
    firstRound.push(seeds.pop());
}
1, 2, 3, 4, 5, 6, 7, 8 => 1, 8, 2, 7, 3, 6, 4, 5

...but在第二轮，种子1遇到种子2和3遇到4。我们需要为每一轮做第一/最后的洗牌。第一次，我们将每个元素分别移动。第二次，我们移动每个元素的对。第三次通过移动组的四个等，直到我们的组大小是seeds.length/2。就像这样：

// this is ruby, aka javascript psuedo-code :)

bracket_list = seeds.clone

slice = 1
while slice < bracket_list.length/2
  temp = bracket_list
  bracket_list = []

  while temp.length > 0
    bracket_list.concat temp.slice!(0, slice)       # n from the beginning
    bracket_list.concat temp.slice!(-slice, slice)  # n from the end
  end

  slice *= 2
end
return bracket_list

下面是数组在迭代过程中的样子(括号表示组大小的增加)：

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

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

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

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

所以现在，在最后8名球员被淘汰后，我们就剩下1, 8, 4, 5, 2, 7, 3, 6了。在倒数第四名被淘汰后，我们得到了1, 4, 2, 3，在最后一轮只有1, 2。

如果不能画一个支架就很难解释.如果我能为你澄清什么，请告诉我。

Answer 3

我用PHP编写了一个解决方案(参见https://stackoverflow.com/a/45566890/760777)。这是javascript版本。

它以正确的位置返回所有种子，。比赛和他的例子是一样的，但是按照更漂亮的顺序，种子1和种子号8都在模式的外部(正如您在网球锦标赛中所看到的)。

如果没有烦心事(这意味着高种子选手总是从低种子选手那里赢)，你将在决赛中获得种子1对2种子。

它实际上做了两件事：

1. 它显示了正确的顺序(这是在正确的位置上打招呼的必要条件)。
2. 它填写正确的位置(如果需要的话)。

关于单个消除括号应该是什么样子的完美解释：http://blog.playdriven.com/2011/articles/the-not-so-simple-single-elimination-advantage-seeding/

8名参与者的代码示例：

​

var NUMBER_OF_PARTICIPANTS = 8; // Set the number of participants

if (!String.prototype.format) {
  String.prototype.format = function() {
    var args = arguments;
    return this.replace(/{(\d+)}/g, function(match, number) { 
      return typeof args[number] != 'undefined' ? args[number] : match;
    });
  };
}

var participants = Array.from({length: NUMBER_OF_PARTICIPANTS}, (v, k) => k + 1) ;
var bracket = getBracket(participants);

console.log(bracket);

function getBracket(participants)
{
  var participantsCount = participants.length;	
  var rounds = Math.ceil(Math.log(participantsCount)/Math.log(2));
  var bracketSize = Math.pow(2, rounds);
  var requiredByes = bracketSize - participantsCount;
	
  console.log("Number of participants: {0}".format(participantsCount));
  console.log("Number of rounds: {0}".format(rounds));
  console.log("Bracket size: {0}".format(bracketSize));
  console.log("Required number of byes: {0}".format(requiredByes));    
    
  if(participantsCount < 2) {
    return [];
  }
    
  var matches = [[1,2]];
  
  for(var round = 1; round < rounds; round++) {
    var roundMatches = [];
    var sum = Math.pow(2, round + 1) + 1;
    
    for(var i = 0; i < matches.length; i++) {
      var home = changeIntoBye(matches[i][0], participantsCount);
      var away = changeIntoBye(sum - matches[i][0], participantsCount);
      roundMatches.push([home, away]);
      home = changeIntoBye(sum - matches[i][1], participantsCount);
      away = changeIntoBye(matches[i][1], participantsCount);
      roundMatches.push([home, away]);
    }
    matches = roundMatches;   
    
  }   
  
  return matches;    
}

function changeIntoBye(seed, participantsCount)
{
    //return seed <= participantsCount ?  seed : '{0} (= bye)'.format(seed);  
    return seed <= participantsCount ?  seed : null;
}

​

将NUMBER_OF_PARTICIPANTS从8更改为6，以获得两次再见。

祝好运。RWC