Printing a single-elimination tournament bracket

How should the teams be arranged in a “seeded” single-elimination tournament bracket?

This question is motivated by the NCAA men’s basketball tournament, the first two rounds of which are now in the books. There are 64 teams in the tournament, divided into four regions each with 16 teams seeded #1 through #16. In typical displays of these regional brackets, such as those on the NCAA and ESPN web sites, the 16 seeds in a region are arranged as shown at left in the figure below, where in this example the favored seed always wins, advancing to the right with each round of the tournament:

Typical layout of seeded 16-team single-elimination tournament bracket.

The basic idea behind this arrangement is that all of the best-seeded teams should be able to advance together for as many rounds as possible, with more advantage granted to higher seeds. More precisely, we want a tournament bracket with r rounds to be fair, defined recursively as follows: the match-ups between the n=2^r teams must be arranged with seed j playing seed n+1-j in the current round, so that assuming the favored seed wins each game, seeds 1 \ldots 2^{r-1} can all advance to the next round, and the remaining bracket is (recursively) also fair.

The above bracket layout has a few visually appealing properties:

  1. In the first round, the favored seed is always the “visiting” team, placed above the lower-seeded opponent.
  2. The #1 seed is always at the top of the bracket in each round.
  3. The #2 seed is (almost, except for property 1) as far from the #1 seed as possible, so that the two top-seeded teams clearly advance “toward” each other in each round.

But this isn’t the only possible fair bracket layout. It’s an interesting problem to count them all. (Hint: even constrained by all three properties above, there are still four different possible layouts, of which the above is just one example.)

For example, consider the following layout, which motivated this post:

Another fair bracket layout generated by several simple algorithms.

This layout is the one that I used to store the history of all past NCAA tournaments since 1985 in the current 64-team format. The layout has the first two properties above, but not the third. I chose it because it’s easy to implement; the following simple Python function generates the ordering of seeds, effectively starting from the single #1 seed as the champion on the right of the bracket and moving left through previous rounds, maintaining the fairness condition as we go:

def bracket_seeds(num_teams):
    seeds = [1]
    while len(seeds) < num_teams:
        games = zip(seeds, (2 * len(seeds) + 1 - seed for seed in seeds))
        seeds = [team for game in games for team in game]
    return seeds

This layout has another “nice” structural interpretation as well: if we temporarily re-index the seeds to start with zero instead of one, then the positions of each seed in the bracket are given by the bit-reversed Gray codes of the seeds.

So, back to the original puzzle: what similarly “nice” algorithm yields the more common layout used by the NCAA, ESPN, etc.? More generally, what other “nice” algorithms yield yet other alternative fair layouts? For example, seems to use the same approach that I did, generating the same layout for brackets with 4, 8, and 16 teams… but the 32-team bracket is different.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.