Cheating at math

Last week I posed a question to myself and my colleagues:

Is there a formula to order the seeds of a single-elimination tournament such that the bracket is "optimal"?

I did a bit of Googling. There were a few generic resources for coaches, and a few academic papers that would take a math degree to decipher. I didn't have that kind of time!

So I cheated. Enter The Online Encyclopedia of Integer Sequences - an invaluable resource for looking up integer sequences. I punched in the first few seeds for a 16-player single-elimination tournament image I had found earlier: 1 16 8 9 4 13. The first result was A208569:

In a knockout competition with m players, arranging the competition brackets ... ensures that highest ranked players cannot meet until the later stages of the competition.

Bingo. This was the formula we were looking for.

A quick bit of coding in Python and we arrive at:

def t(L, k):
  if k == 1:
    return 1
  m = (k - 1) & -(k - 1)
  return 1 + L // m - t(L, k - m)

def bracket_optimal_seed_order(num_rounds):
  L = 2 ** num_rounds
  return [t(L, i + 1) for i in range(L)]

To test out the code:

print(bracket_optimal_seed_order(1))
print(bracket_optimal_seed_order(2))
print(bracket_optimal_seed_order(3))
print(bracket_optimal_seed_order(4))

Log

These results line-up with A208569, our example sequence 1 16 8 9 4 13 ..., and most brackets found online. ¹

The full code is posted here as a gist.

This formula is now being used to create our bracket ordering for the Python Package Tournament.

---

1. There are multiple optimal top-to-bottom orderings for a tournament bracket. For example, the order can be reversed and all of the matchups will be the same. But topologically, they are all equivalent.↩