javascript - 排序锦标赛种子

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 等组中的前 4 名选手在半决赛之前互相比赛。因此，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

从上到下匹配玩家的思路是正确的，但还不够完善。做一次对第一轮非常有效:

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

...但是在第二轮中，种子 1 遇到种子 2，种子 3 遇到种子 4。我们需要为每一轮进行第一次/最后一次洗牌。第一次，我们单独移动每个元素。第二次，我们移动每个 PAIR 元素。第三次，我们移动四人一组，等等，直到我们的组大小为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。后 4 名被淘汰后，我们有 1, 4, 2, 3，在最后一轮只有 1, 2。

如果不画括号就很难解释这个……如果我能为你澄清一些事情，请告诉我。