4

I am looking for algorithms to make single elimination and double elimination brackets.

The first step was figuring out the seeding algorithm, byes included, which I found in several places in SO: here (where byes can be introduced simply b replacing the last n excess teams and shifting the seed positions n times) and here (byes are baked in, and I only need to shift the positions).

Which is an improvement over the algorithm I was using which paired teams like this: [(x, -x - 1) for x in range(num_players / 2)] and instead of defining the next round as one would expect: Winner Match_i vs Winner Match_i+1 it would be Winner Match_i vs Winner Match_n-i, quite unintuitive and harder to maintain.

But now I am trying to define the algorithms to make the brackets. I am having trouble to find actual algorithms to generate single elimination brackets and double elimination brackets.

I am not too worried about single elimination bracket generation because it is pretty straightforward, even with byes and also considering I am supporting different consolation modes.

But the double elimination brackets are throwing me off. Everywhere I look at they are being built in a different manner. And it is not just that I cannot choose one of them, it is also that I cannot figure out how to make the associations between matches, especially when byes are involved because they break the bracket structure and makes the problem harder to solve.

I would post my code but it is pretty long, messy and it has some bugs where teh bracket is not being generated correctly, that is why I am looking for more reliable bracket generation algorithms.

2
  • 2
    You're not giving us much to go on. What, actually, are your requirements? Put another way: why, specifically, isn't "randomly throw all applicants onto the leaves of a binary tree" good enough? Jun 30 '17 at 9:35
  • @well because they are seeded/fillable brackets, not blind draw ones
    – dabadaba
    Jun 30 '17 at 10:07
4

Since giving you the code and pointing you to a resource are both off topic I will attempt to show you how to make it much easier to write your own solution to this problem.

Rather than make yourself dizzy pouring over published solutions to the programming problem, consult a domain expert:

There are two ways to run single or double elimination tournaments --- either "Blind Draw" or "Seeded".

Seeded Tournaments are usually run with a league or season event so that skill level can be determined.

The number one ranked team players the lowest ranked seed, the number two ranked team plays the second lowest ranked seed and so on.

You will need to estimate the number of teams to determine if you want a Single or Double elimination tournament. After this has been determined, follow the rules of Single or Double elimination tournaments.

erasabletournamentbrackets.com - Seeded Tournaments

This means that to make it seeded we need to put the teams in order of rank before the bracketed tournament begins. If we leave them placed randomly then it's blind. Sounds like all we need to do is add a sorting step when doing seeded. After that we should be able to use the same code for both seeded and blind.

Double Elimination Tournament Chart - Blind Draw - 16 Player Field Double Elimination Tournament Chart - Seeded - 16 Player Field

Compare these two carefully and you'll see that indeed they work very similarly. The difference being the ordering. 1 plays 16 is a good way to build the matches because all you have to do is rank them in order and then match the best with worst. This best to worst pattern repeats as we go from round to round. This ensures that if the winner is always the highest ranked then 1 doesn't face 2 for as long as possible. It should be possible to generalize this for any power of 2.

That can all be managed by sorting the winners from the last round according to their pre-tournament rank and doing it all again. Also do this for the losers and you have the next round of loser side of the double elimination.

Finish it all by having the winner of the winners face the winner of the losers.

So lets say you can make all that work. What about byes?

bye 1 |bī| noun 1 the transfer of a competitor directly to the next round of a competition in the absence of an assigned opponent.

[From the New Oxford American Dictionary.]

For simulating a tournament with byes I'd reach for my favorite pattern. The null object pattern can let you leave all the previous code alone by simply creating a null competitor that represents the absence of an assigned opponent. How? They always loose. This way you can have brackets that DON'T start with a power of 2. Like say 12:

Double Elimination Tournament Chart - Seeded - 12 Player Field

Look carefully at that and you may notice what it has in common with the 16 player seeded field. Everything is the same except some spots have been erased. Those erased spots are where to put the null object players who always loose.

To make that work for printing you'll simply suppress printing a bracket that has a null object player in it.

This means you're free to do your byes in the first round or any round all without changing your code just by introducing players who always loose and don't print their bracket.

With these byes it should be possible to generalize this for any number of competitors.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.