排序锦标赛种子 [英] sorting tournament seeds

问题描述

我正在制作一个HTML / JS驱动的单/双消除支架Web应用程序。我正在努力弄清楚如何从种子队/球员名单中分配第一轮比赛。例如，在8名玩家的支架中，第一轮比赛是：

I'm making a HTML/JS powered single/double elimination bracket web app. I am struggling to figure out how to assign the first round matches from a list of seeded teams/players. For example, in a bracket of 8 players the first round matches are:

1v8
4v5
2v7
3v6

1v8 4v5 2v7 3v6

在更通用的术语中，种子可以被认为是一个数组（因为我通过弹出一个数组来指定团队匹配）：
1,2,3， 4,5,6,7,8

In more generic terms, the seeds can be thought of as an array(as I assign teams to matches by popping them off an array): 1,2,3,4,5,6,7,8

需要分类到：
1,8,4,5,2,7,3,6

which needs to be sorted to: 1,8,4,5,2,7,3,6

为了澄清，较高的种子需要在排序的数组中具有它们之间的最大距离，这是因为在没有扰乱的括号中，较低的种子被淘汰首先和高种子匹配尽可能晚。实际上，想想一个网球锦标赛，你想要阻止16或32等支架的前4名球员互相比赛直到半决赛。因此， 16 种子支架的正确数组输出为：

To clarify, the higher seeds need to have the maximum distance between them in the sorted array, this is so that in a bracket with no upsets, lower seeds get knocked out first and and matches with high seeds occur as late as possible. In practical terms, think of a tennis tournament, where you want to prevent the top 4 players in a bracket of 16 or 32 etc from playing each other until the semi finals. So, the correct array output for a 16 seed bracket is:

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

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

转换为以下第一轮比赛：

which translates to the following 1st round matches:

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

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

感谢Matt Ball提供8种子支架的正确算法

Thanks to Matt Ball for the correct algorithm for an 8 seed bracket

推荐答案

我想出了一个解决方案，但它不在排序数组的范围之内。

I've come up with a solution, but it's outside the scope of just "sorting arrays".

（javascript）代码位于 http://jsbin.com/ukomo5/2/edit。

The (javascript) code is at http://jsbin.com/ukomo5/2/edit.

在基本术语中，算法假设括号中不会出现任何扰乱，因此种子1和2 应在最后一轮中相遇。它遍历每轮中的每个种子（从预先计算的总决赛开始，向后工作），计算当前种子（在迭代中）赢得的前一轮中的未知种子。这可以做到，因为给定种子和圆数，你可以计算出其他种子应该是什么：

In basic terms, the algorithm assumes that no upsets will occur in the bracket, therefore seeds 1 and 2 should meet in the final round. It iterates through each seed in each round (starting from the pre-calculated grand final, working backwards), calculating the unknown seed in the match in the previous round that the current seed (in the iteration) had won. This can be done because given a seed and round number, you can work out what the other seed should be:

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

为了说明，在半决赛中：

To illustrate, in the semifinals:

半决赛1（其中）已知种子是1）：其他种子= 4 + 1 - 1 = 4

Semifinal 1 (where known seed is 1): other seed = 4 + 1 - 1 = 4

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

Semifinal 2 (where known seed is 2): other seed = 4 + 1 - 2 = 3

我在看到我画的无心烦括号时才注意到这种模式。

I just noticed this pattern when looking at a "no upsets" bracket I had drawn.

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

In the final iteration (ie round 1) all seeds and their position are known, ready to be assigned to matches. The correct sorted array is below:

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

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

再次感谢Matt Ball为小支架提出了正确的解决方案（如果没有详细的背景，很难说明问题和所需的解决方案，我没有在我最初的问题中完全没有。）

Thanks again to Matt Ball who came up with a correct solution for small brackets (It's difficult to state the problem and desired solution without detailed context, which I didn't do completely in my initial question).

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

If anyone has another solution or a more elegant version of my solution let us know!

这篇关于排序锦标赛种子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！