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

Answer 3

First off, I would create some classes for Teams and Matchups to better represent your problem and make it easier to manipulate data.

( Working example at: https://dotnetfiddle.net/Z1CJib )

public class Team
{
    public Team(string name, int seed){
        Name = name;
        Seed = seed;
    }

    public string Name {get; set;}

    public int Seed {get; set;}

    //simple method to compare two teams' seed values and return the better (1 > 2) team
    public static Team GetBetterSeed(Team t1, Team t2){
        return t1.Seed < t2.Seed ? t1 : t2;
    }
}

public class Matchup
{
    public Matchup(Team t1, Team t2){
        Team1 = t1;
        Team2 = t2;
    }

    public Team Team1 {get; set;}
    public Team Team2 {get; set;}

    //"Team 1's Name vs. Team 2's Name"
    public override string ToString(){
        return Team1.Name + " vs. " + Team2.Name;
    }

    //using the GetBetterSeed() method above we can get which team out of a matchup is favored
    public Team GetFavored(){
        return Team.GetBetterSeed(Team1, Team2);
    }
}

Now you can create a set of Teams that will have names and seeds values

var newTeam = new Team("Team Name", 1);
teamList.Add(newTeam);

or however you want to create a list of teams.

---

Your matchup algorithm actually works (so long are your team count is even), I just separated out the team creation from the matchups:

private static List<Matchup> CreateMatchups(List<Team> teams)
{
    var matchups = new List<Matchup>();

    for (int i = 0; i < teams.Count / 2; i++)
    {
        matchups.Add(new Matchup(teams[i], teams[teams.Count - (i+1)]));
    }

    return matchups;
}

To print your matchups in order you can use Linq's OrderBy. You give OrderBy a function telling it what part of an item you want to order by (in this case Team.Seed) and it will give the set to you ordered least to greatest by that value:

private static void PrintBracket(List<Matchup> Matchups)
{
    foreach(var matchup in Matchups.OrderBy(x=> x.GetFavored().Seed)){
        Console.WriteLine(matchup);
    }
}