Generating a Direct Elimination (DE) Table in Linear Time

(This was originally published on Pop Art’s employee blog on Feb 8, 2012. Pop Art was a digital marketing agency where I worked, and is now a SaaS company, BAM!).

One of my pet projects involves creating a “direct elimination table” — the tables that are used in sporting competitions to match up teams or competitors until only one is left.

The logic behind a direct elimination table is based on a very boring “ideal” competition: one where there are no surprises. The first seed wins, the second seed comes in second, and so on. In this ideal competition, at every round, the highest seed pairs off against the lowest seed, and the second-highest seed pairs off against the second-lowest seed, etc. Starting with the winner and working backwards, it’s easy enough to construct a direct elimination table. However, what if you had to start at the bottom? How do you pair competitors up?

I started by looking at established elimination tables, trying to infer a pattern. For example, in a table of sixteen, the pairings look like this: 1 vs. 16, 9 vs. 8, 5 vs. 12, 13 v. 4, 3 vs. 14, 11 vs. 6, 7 vs. 10, and 15 vs. 2. After puzzling over it for a while, I could detect no discernible pattern. So I turned to the subject of today’s blog post: the excellent On-Line Encyclopedia of Integer Sequences (OEIS).

The OEIS is a brilliant database that contains pretty much every sequence known to mathematics. Often, the sequence you’re looking for will match more than one sequence, which makes it a great learning tool for exploring different generating functions. Entering my direct elimination sequence (1, 16, 9, 8, 5, 12, 13, 4, 3, 14, 11, 6, 7, 10, 15, 2) didn’t yield any results. However, there’s obviously order in the sequence because of the way it’s generated. Undaunted, I converted it to a zero-based list for simplicity, and examined the sequence in binary. It was then I noticed a definite trend: every other element could be generated by taking the binary complement of the previous element. The odd-numbered elements are trickier: with them, you fix some number of most-significant bits and take the compliment of the rest. A mystery! Here’s the binary representations and the algorithm to generate the next element for a direct elimination table of 16:

Zero-based    Binary            Algorithm to generate 
seed number   representation    next element
-----------   --------------    --------------------------------
    0             0000          Take complement
   15             1111          Fix 1, take complement
    8             1000          Take complement
    7             0111          Fix 2, take complement
    4             0100          Take complement
   11             1011          Fix 1, take complement
   12             1100          Take complement
    3             0011          Fix 3, take complement
    2             0010          Take complement
   13             1101          Fix 1, take complement
   10             1010          Take complement
    5             0101          Fix 2, take complement
    6             0110          Take complement
    9             1001          Fix 1, take complement
   14             1110          Take complement
    1             0001

To my eye, the number of binary digits you have to fix doesn’t have a particular pattern…but hey, let’s plug it into OEIS! Sure enough, 1, 2, 1, 3, 1, 2, 1 does indeed match a sequence: the ruler function. And it turns out to be exactly what I’m looking for. I then verified it held for a table of 32 and 64. Proving that the sequence will hold for a table of any size I will leave as an exercise for the reader.

With the ruler function in hand, it’s possible to easily generate the lineup for a direct-elimination table of any size, in linear time. Which is exactly what I needed for my project.