Double Elimination Tournament Algorithm for byes %4

Question

I'm trying to code a Double Elimination tournament where the brackets are based on mod 4. The first round should handle all of the byes so that after round 2 there will be no more byes. I'm having a hard time trying to figure out the actual math behind determining the amount of byes I need. If anyone can help me with the math behind this it would be greatly appreciated.

There are 4 possible answers for anything mod 4 (0,1,2,3) I need to handle byes for 1,2,3.

An example of what I mean is 13 players so (13%4=1) so the round 1 bracket should look like 1vs2 2vs3 3vs4 4vs5 5vs6

and round 2 is 7vs winner 8vs winner 9vs winner winner vs winner and then you have the losers bracket

Basically if your familiar with the website Challenge, I want to generate my brackets similar to them, but I can't figure out the math behind their determining of the byes.

If anybody has done something similar to this I would greatly appreciate his help.

Answer 1

Where N is the number of competitors, the number of rounds will be:

nRounds = Math.Ceiling( Math.Log( N, 2 ) );

The number of slots in the first round will be:

firstRoundSlots = Math.Pow( 2, nRounds );

The top competitors get byes, so in your example, there are 13 competitors in the round of 16, so the top 3 competitors get byes. In other words, the number of byes are firstRoundSlots - N.

The order of the bouts is a little more complicated. Basically the idea is that the finals bout is the best competitor vs. the second-best competitor. In the semifinal, the best competitor squares off against the third best competitor, and the second best competitor squares off against the 4th best competitor. And so on and so forth. So it's easiest to work backwards from the finals to generate the order.

However, if you want to know an algorithm for generating the bout orders in reverse (i.e., starting with round 1 and working your way towards the finals), I wrote a blog post about that here:

http://blogs.popart.com/2012/02/things-only-mathematicians-can-get-excited-about/

Answer 2

I'll work you through how I solved this.
You want a number of players in round 2 that is a power of 2.

The number of players in round 2 is: (matches in round 1)/2 + byes)
Let P be the number of players.

2^n = (P-byes)/2 + byes
2^(n+1) = P-byes + 2*byes
2^(u) = P + byes

So find the smallest u s.t. 2^u >= P, there are then 2^u-P byes.

example cases: 7 -> 2^u=8 -> (8-7) -> 1 bye
1 bye, 3 matches -> 4 players in round 2

It's not mod 4, compare 9 players to 13: 9 -> 2^u=16 -> (16-9) -> 7 byes 13 -> 2^u=16 -> (16-13) -> 3 byes

A more interesting question would be how to arrange for the minimum number of byes, allowing for some in other rounds than the first.

Answer 3

Simplest algorithm I can think of:

1. Seed the players (either using actual information or some random thing)
2. Rank of a player depends on current points, and if that is a tie, then on seed
3. At every stage of the tournament, starting from top ranked player to the least ranked, pair each player with the next highest ranked player they have not played with
4. The least ranked player usually gets the bye
5. Whenever one person loses a total of two games (or two loss equivalents in case where draw is prevalent), then that person is out of the tournament
6. Repeat this until there is a single player left in the tournament