排序锦标赛种子

Question

我正在制作一个HTML/JS动力的单/双消除括号网页应用程序。我正在努力想出如何从种子球队/球员列表中分配首轮比赛。例如，在8名玩家的托架的第一轮比赛是：

1V8 4V5 2V7 3V6

在更一般的术语中，种子可被认为是一个阵列（如我分配队通过将它们从阵列中弹出来进行匹配）： 1,2,3,4,5,6,7,8

需要对其进行排序： 1,8,4,5,2,7,3 ，6

为了澄清，较高的种子需要它们之间的最大距离在s这是因为在一个没有干扰的支架中，较低的种子会首先被淘汰，而与高的种子匹配则会尽可能晚地发生。实际上，想象一下网球比赛，你想阻止16或32等的支架中的前四名选手互相比赛直到半决赛。因此，种子支架的正确的阵列输出是：

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

其转换为下面的第一回合：

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

感谢马特·鲍尔正确的算法的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

感谢马特Ball为小括号提出了正确的解决方案（在没有详细的上下文的情况下，我很难说明问题和期望的解决方案，但在最初的问题中我没有这样做）。

如果有人有我的解决方案的另一个解决方案或更优雅的版本让我们知道！

Answer 2

这可能不是效率如同 @ alex的回答使用自定义sort功能，但肯定更容易编写和理解：

// This algorithm assumes that seeds.length is an even number 
var seeds = [1, 2, 3, 4, 5, 6, 7, 8], 
    firstRound = []; 

while (seeds.length) 
{ 
    firstRound.push(seeds.shift()); 
    firstRound.push(seeds.pop()); 
} 

// seeds is now empty 
// firstRound is now [1, 8, 2, 7, 3, 6, 4, 5] 

Demo 1

---

其实，我只是想更快的算法（就地“排序”中，需要O(n)时间）：

// Also assumes that seeds.length is an even number 
var seeds = [1, 2, 3, 4, 5, 6, 7, 8], 
    numSeeds = seeds.length, 
    stop = numSeeds >> 1, 
    temp; 

for (var i=1; i<stop; i=i+2) 
{ 
    temp = seeds[i]; 
    seeds[i] = seeds[numSeeds-i]; 
    seeds[numSeeds-i] = temp; 
} 

// seeds is now [1, 8, 3, 6, 5, 4, 7, 2] 

Demo 2

注意，无论这些算法产生恰好对作为OP相同顺序，但它们都产生相同的设置对：

• (1,8)
• (2,7)
• (3,6)
• (4,5)

Answer 3

从顶部和底部匹配球员的想法是正确的，但不完全。做一次第一轮的伟大工程：

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 4

这是我开发的算法。第一步是绘制一个表格，其中包含多个行（有四个队伍）（四舍五入为2）以及所需的列数，以表示二进制队的数量。比方说，有8支队伍。该表最初看起来像这样（点代表水平单元格边界）：

。 。 。 | | | | 。 。 。 | | | | 。 。 。 | | | | 。 。 。 | | | | 。 。 。 | | | | 。 。 。 | | | | 。 。 。 | | | | 。 。 。 | | | | 。 。 。

列按从小到大的顺序编号。每列在每2 ^（列号）行放置一个星号。也就是说，第1列中的每第2行，第2列中的每第4行等。

。 。 。 | | | | 。 。 。 | | | | *。 。 | | | | 。 。 。 | | | | * *。 | | | | 。 。 。 | | | | *。 。 | | | | 。 。 。 | | | |

---

在第1行的每列中以0开头。之后，每列中的连续行从0-1和1-0开始切换，除非该行中有星号。这是结果：

。 。 。 | 0 | 0 | 0 | 。 。 。 | 1 | 1 | 1 | *。 。 | 1 | 0 | 0 | 。 。 。 | 0 | 1 | 1 | * *。 | 0 | 1 | 0 | 。 。 。 | 1 | 0 | 1 | *。 。 | 1 | 1 | 0 | 。 。 。 | 0 | 0 | 1 |

---

最后一步是评估每行将0和1的字符串视为二进制数字。这将导致0-7的值。给每个加1会得到1-8的值。这些对应于种苗。

。 。 。 | 0 | 0 | 0 | + 1 = 1 。 。 。 | 1 | 1 | 1 | + 1 = 8 *。 。 | 1 | 0 | 0 | + 1 = 5 。 。 。 | 0 | 1 | 1 | + 1 = 4 * *。 | 0 | 1 | 0 | + 1 = 3 。 。 。 | 1 | 0 | 1 | + 1 = 6 *。 。 | 1 | 1 | 0 | + 1 = 7 。 。 。 | 0 | 0 | 1 | + 1 = 2

---

每对种子是为了要播放的比赛。即。 1-8，5-4，3-6和7-2。这可以扩展到任何数量的种子。当由于条目的数量小于2的幂而插入了脚趾时，它们采用最高的种子值。例如。如果只有28个条目，那么脚本将分配给29,30,31和32的位置。

Answer 5

我在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; \t 
 
    var rounds = Math.ceil(Math.log(participantsCount)/Math.log(2)); 
 
    var bracketSize = Math.pow(2, rounds); 
 
    var requiredByes = bracketSize - participantsCount; 
 
\t 
 
    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