生成种子锦标赛支架

Question

我一直在对这个主题进行大量研究，虽然我发现了许多与我类似的问题，但我还没有找到我正在寻找的答案。我正在创建一个种子单淘汰锦标赛支架。这种类型的括号规则规定，最好的两支球队将参加决赛。例如，如果我们有 8 个团队，其中第 1 队最好，第 8 队最差。

如果我们有 8 个团队，它将导致：

第 1 轮 ==========> 第 2 轮 ==========> 第 3 轮 1
队 vs 8
队 4 队 vs 5 队 ==> 1 队 vs 4 队 ==> 1 队 vs 队团队 2
团队 3 对团队 6 ==> 团队 3 对团队 2
团队 2 对团队 7

请注意第 1 轮中的团队顺序，因为我的问题将围绕正确的团队顺序展开。您将看到团队 1 位于顶部，团队 2 位于底部。

现在我想出了一个简单的函数，它可以在第 1 轮中配对团队以产生正确的对决：

//Bracket Structure represents the order of teams in which they should be printed in round 1 for specific number of teams.  
//As you see I have to manually specify for each team size, I wish to write an algorithm that will calculate this for me so that I do not have a maximum teams restriction.
private static readonly Dictionary<int, int[]> BracketStructure = new Dictionary<int, int[]>
{
    //2 is number of teams, 0 represents the team in the array, so 0 is actually team 1, 1 is team 2, etc...
    { 2, new [] { 0 } },
    { 4, new [] { 0, 1} },
    { 8, new [] { 0, 3, 2, 1} },
    { 16, new [] { 0, 7, 4, 3, 2, 5, 6, 1} },
    { 32, new [] { 0, 15, 7, 8, 3, 12, 4, 11, 1, 14, 6, 9, 2, 13, 5, 10 }},
    { 64, new [] { 0, 31, 16, 15, 8, 23, 24, 7, 3, 28, 19, 12, 11, 20, 27, 4, 1, 30, 17, 14, 9, 22, 25, 6, 2, 29, 18, 13, 10, 21, 26, 5 }}
};

private static void CreateMatchups(int totalTeams)
{
    var teams = new List<int>();
    var matchups = new List<string>();
    var c = 1;
    while (totalTeams >= c)
    {
        teams.Add(c);
        c++;
    }

    for (var i = 0; i < teams.Count/2; i++)
    {
        matchups.Add(teams[i] + " vs " + teams[totalTeams - (i + 1)]);
    }
    PrintBracket(matchups, BracketStructure[totalTeams]);
}

private static void PrintBracket(IReadOnlyList<string> matchups, IEnumerable<int> teams)
{
    foreach (var team in teams)
    {
        Console.WriteLine(matchups[team]);
    }
}

上面代码的问题在于它不会以正确的顺序打印它们。订单将是：

团队 1 对团队 8
团队 2 对团队 7
团队 3 对团队 6
团队 4 对团队 5

我似乎无法提出以种子方式对这些进行排序的算法。这需要在任何地方工作，从 2 人锦标赛到任何数字真的......任何帮助或建议都非常感谢。

我的订购基于http://www.printyourbrackets.com/

我最初将其发布在https://softwareengineering.stackexchange.com/ 上，但有人告诉我堆栈溢出是解决此问题的正确位置，因此我将其发布在这里。

有关什么是种子支架的更多信息，您可以在这里阅读：https : //en.wikipedia.org/wiki/Seed_(sports)

编辑：

我在做更多研究时遇到了这个问题：https : //jsfiddle.net/vrnb16r9/1/

游戏在那里以正确的顺序打印出来，差不多，但我相信他的公式仍然准确。例如，在我上面的 8 个团队示例中，它将像这样打印，这是正确的顺序：

第 1 轮 ==========> 第 2 轮 ==========> 第 3 轮 1
队 vs 8
队 4 队 vs 5 队 ==> 1 队 vs 4 队 ==> 1 队 vs 队团队 2
团队 3 对团队 6 ==> 团队 3 对团队 2
团队 2 对团队 7

然而，他的公式打印出来是这样的：

第 1 轮 ==========> 第 2 轮 ==========> 第 3 轮 1
队 vs 8
队 4 队 vs 5 队 ==> 1 队 vs 4 队 ==> 1 队 vs 队团队 2
团队 2 对团队 7 ==> 团队 2 对团队 3
团队 3 对团队 8

注意到第 2 队上升了一次，第 3 队下降了一次吗？虽然他的公式在每一轮中仍然会导致正确的配对，但它并不是 100% 有正确的顺序。我意识到他只是交换了两支球队的位置，最终并不重要，因为无论如何，下一轮都会有正确的对决，但是我仍然很想弄清楚如何按照他们假设的确切顺序来安排他们，就像打印我上面给出的括号链接一样。我相信他的方法是正确的方向，找出胜利者并倒退，但是我在理解他的代码时遇到了一些麻烦。

编辑2：

我已经开始赏金，因为我仍然对此感到非常迷茫，并且很难将逻辑放在一起。我基本上希望获得有关如何实现我上面讨论的内容的 ac# 代码示例。

Answer 1

我将发布一个代码，我认为它可以满足您的需求，但排序并不如您所愿。我认为 printyourbracket.com 上的那些表格是手工制作的，而不是算法制作的（我还查看了 16 和 32 版本）。总而言之，这里是代码。首先定义小类，以便于阅读代码：

class Round {
    public Match[] Matches { get; set; }
}

class Match {
    // where number is player's seed number        
    public int PlayerA { get; set; }
    public int PlayerB { get; set; }
}

这是算法：

    static Round[] Generate(int playersNumber) {        
        // only works for power of 2 number of players   
        var roundsNumber = (int) Math.Log(playersNumber, 2);
        var rounds = new Round[roundsNumber];
        for (int i = 0; i < roundsNumber; i++) {
            var round = new Round();
            var prevRound = i > 0 ? rounds[i - 1] : null;
            if (prevRound == null) {
                // if first round - result is known
                round.Matches = new[] {
                    new Match() {
                        PlayerA = 1,
                        PlayerB = 2
                    }
                };
            }
            else {
                round.Matches = new Match[prevRound.Matches.Length*2];
                // find median. For round 2 there are 4 players and median is 2.5 (between 2 and 3)
                // for round 3 there are 8 players and median is 4.5 (between 4 and 5)
                var median = (round.Matches.Length*2 + 1)/2f;
                var next = 0;
                foreach (var match in prevRound.Matches) {
                    // you can play here by switching PlayerA and PlayerB or reordering stuff
                    round.Matches[next] = new Match() {
                        PlayerA = match.PlayerA,
                        PlayerB = (int) (median + Math.Abs(match.PlayerA - median))
                    };
                    next++;
                    round.Matches[next] = new Match() {
                        PlayerA = match.PlayerB,
                        PlayerB = (int) (median + Math.Abs(match.PlayerB - median))
                    };
                    next++;
                }
            }
            rounds[i] = round;
        }
        return rounds.Reverse().ToArray();
    }

用法：

var rounds = Generate(8);
foreach (var round in rounds) {
     foreach (var match in round.Matches) {
         Console.WriteLine("{0} vs {1}", match.PlayerA, match.PlayerB);
     }
     Console.WriteLine();
}
Console.ReadKey();

基本上我们从根 (1,2) 开始，然后倒退，将高等级玩家匹配到最低等级，将第二高匹配到第二低，依此类推。从您的描述来看，它就像在那个 javascript 算法中一样，尽管没有查看它们的实现。您可以使用此代码来尝试实现您想要的排序，但如果这些表是由人类制作的 - 这可能是不可能的。