排序锦标赛种子

Question

我正在制作一个HTML/JS驱动的单/双消除支架Web应用程序.我正在努力弄清楚如何从种子队/球员名单中分配第一轮比赛.例如,在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.

如果不能画出一个括号,很难解释这一点......如果我能为你澄清一些内容,请告诉我.

Answer 2

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

(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 Ball），他为小括号提出了正确的解决方案（如果没有详细的上下文，很难陈述问题和所需的解决方案，我在最初的问题中没有完全做到这一点）。

如果有人有其他解决方案或更优雅的版本，请告诉我们！