Generating a Seeded Tournament Bracket

Question

I've been doing a lot of research on this topic, and while I have found many questions similar to mine, I haven't quite found the answer I am looking for. I am creating a Seeded Single Elimination Tournament bracket. The rules for this type of bracket state that the two best teams will play in the finals. So for example if we had 8 teams with Team 1 being the best and Team 8 the worst.

If we had 8 teams it will result in:

Round 1 =========> Round 2 =========> Round 3
Team 1 vs Team 8
Team 4 vs Team 5 ==> Team 1 vs Team 4 ==> Team 1 vs Team 2
Team 3 vs Team 6 ==> Team 3 vs Team 2
Team 2 vs Team 7

Please note the order of teams in round 1 as my question is going to evolve around having the correct order of teams. You will see that team 1 is at the top and team 2 is at the bottom.

Now I have figured out a simple function which will pair teams up in round 1 to produce correct matchups:

//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]);
    }
}

The problem with the above code is that it will not print them in the correct order. The order will be:

Team 1 vs Team 8
Team 2 vs Team 7
Team 3 vs Team 6
Team 4 vs Team 5

I can't seem to come up with the algorithm that will sort these in a seeded fashion. This needs to work for anywhere form a 2 man tournament to any number really... Any help or advise on this is most appreciated.

I have been basing my ordering on http://www.printyourbrackets.com/

I posted this originally on https://softwareengineering.stackexchange.com/ but I was told stack overflow is the right place for this question so I'm posting it here instead.

For more information on what a seeded bracket is, you can read here: https://en.wikipedia.org/wiki/Seed_(sports)

EDIT:

I came accross this as I was doing more research: https://jsfiddle.net/vrnb16r9/1/

The games are printed out in the correct order there, well almost, but I believe that his formula there is still accurate. For example with my 8 team example above it will be printed like this which is the correct order:

Round 1 =========> Round 2 =========> Round 3
Team 1 vs Team 8
Team 4 vs Team 5 ==> Team 1 vs Team 4 ==> Team 1 vs Team 2
Team 3 vs Team 6 ==> Team 3 vs Team 2
Team 2 vs Team 7

However his formula prints it out like this:

Round 1 =========> Round 2 =========> Round 3
Team 1 vs Team 8
Team 4 vs Team 5 ==> Team 1 vs Team 4 ==> Team 1 vs Team 2
Team 2 vs Team 7 ==> Team 2 vs Team 3
Team 3 vs Team 8

Notice that team 2 got moved up once and team 3 dropped down once? While his formula still leads to correct pairings in each round it doesn't 100% has the correct order. I realize that he just swapped the two teams position and it ultimately doesn't matter because no matter what, the next round will have correct matchups, However I would still love to figure out how to have them in the exact order they are suppose to, just like on print your bracket link I gave above. I believe his approach is in the right direction, figure out the winner and work your way backwards, however I'm having a little trouble understanding his code.

EDIT 2:

I've started a bounty because I'm still very lost with this and had very little luck putting together the logic. I'm basically hoping to get a c# code example on how to achieve what I've discussed above.

Answer 1

I'll publish a code which I think does what you want, but ordering is not exact as you wish. I think those tables on printyourbracket.com were crafted by hand, not by algorithm (I also looked at 16 and 32 version). All in all, here is the code. First define small classes to make it easier to read code:

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; }
}

And here is the algorithm:

    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();
    }

Usage:

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();

Basically we start at root (1,2) and go backwards, matching high rank players to lowest ranks, second highest to second lowest and so on. From your description it's like in that javascript algorithm, though didn't look at their implementation. You can play with this code to try to achieve ordering you want, but if those table were made by humans - that might be not possible.

Answer 2

You can get the correct ordering using recursion. Fewer lines of code as well.

(fiddle https://dotnetfiddle.net/nD8dXb)

Recursive function:

public static void branch(int seed, int level, int limit) {
    var levelSum = (int) Math.Pow(2, level) + 1;

    if (limit == level + 1) {
        Console.WriteLine("Seed {0} vs. Seed {1}", seed, levelSum - seed);
        return;
    }
    else if (seed % 2 == 1) {
        branch(seed, level + 1, limit);
        branch(levelSum - seed, level + 1, limit);
    }
    else {
        branch(levelSum - seed, level + 1, limit);
        branch(seed, level + 1, limit);
    }
}

Call it for each round:

var numberTeams = 16;   // must be a power of 2
var limit = (int) (Math.Log(numberTeams, 2) + 1);

for (int round = 1; round < limit; round++) {
    Console.WriteLine("Round #{0}", round);
    branch(1, 1, limit - round + 1);
    Console.WriteLine();
}

Output:

Round #1
Seed 1 vs. Seed 16
Seed 8 vs. Seed 9
Seed 5 vs. Seed 12
Seed 4 vs. Seed 13
Seed 3 vs. Seed 14
Seed 6 vs. Seed 11
Seed 7 vs. Seed 10
Seed 2 vs. Seed 15

Round #2
Seed 1 vs. Seed 8
Seed 4 vs. Seed 5
Seed 3 vs. Seed 6
Seed 2 vs. Seed 7

Round #3
Seed 1 vs. Seed 4
Seed 2 vs. Seed 3

Round #4
Seed 1 vs. Seed 2