0
$\begingroup$

I'm designing a web app to host e-sports tournaments and want to create an algorithm that generates tournament brackets.

Given a list of participants' user ID's (minimum 4, maximum let's say 64), I want to generate a bracket in the form of a list of pairings, where each element of the pair represents a match participant or a reference to the winner of a previous match, i.e. User 1 vs. User 2, Winner of match 1 vs. User 3, and so on.

A simple example, given the array of entrants:

(user1, user2, user3, user4)

We get the end result as a set of pairs, in the logical order:

(user1, user2), (user3, user4), (winner0 vs winner1)

Where winner0 refers to the winner of match 0 (the first pair in the result set). Thus, the winner of the last match in the set is the winner of the tournament.

I need this to work with any size entrant list between 4 and 64 (or some other theoretical maximum), not just for powers of 2. When the entrant count is not a power of 2, some entrants must get one more or one fewer match in order to fill in the entire bracket. All initial placements will be random.

I suppose it's also possible to represent the result as a binary tree, but I'm not sure I will be able to apply it that way.

$\endgroup$
  • $\begingroup$ What have you tried and where did you get stuck? Are you aware that tournaments suck at ordering participants? Have you checked out pool systems, or Swiss systems? $\endgroup$ – Raphael Jul 23 '17 at 10:19
  • $\begingroup$ I've been able to set up brackets where the number of entrance is a power of 2, but I'm stumped as to how to make it work with any number of entrants. $\endgroup$ – Derek Jul 23 '17 at 12:01
  • $\begingroup$ My app does include a numerical rating system (similar to ELO) for each player, and I have been looking at some form of different bracket system that gets players better opponents based on rating. Product owner wants brackets though. $\endgroup$ – Derek Jul 23 '17 at 12:05
  • 2
    $\begingroup$ Do you have any requirements on the particular tournament? Any objective function you are trying to maximize? Otherwise literally any binary tree with one leaf per participant works, so you're just asking "given $n$, how do I construct a binary tree with $n$ leaves?". $\endgroup$ – D.W. Jul 23 '17 at 16:35
  • $\begingroup$ That is correct, but the stumbling block with a binary-tree representation is how to store the result in a MySQL table. $\endgroup$ – Derek Jul 26 '17 at 15:01
1
$\begingroup$

Create a new node for each entrant, then put a pointer to each such node in a FIFO queue. Remove the two pointers $p_1, p_2$ in front of the queue, then create a new node with children $p_1$ and $p_2$, and enqueue a pointer to it. Repeat until the queue size is $1$. The one element you're left with is the root of a binary tree that encodes the bracket.

$\endgroup$
  • $\begingroup$ I like this idea. The reason I used references in matches as I described above is because I need to be able to store the end result in a SQL table, and I'm not sure how I'd do that with this kind of result. $\endgroup$ – Derek Jul 23 '17 at 12:03
0
$\begingroup$

I worked on a PHP / Laravel plugin that generates brackets with / without preliminary round robin. Maybe it can be useful to you, I don't know what tech you are using. Here is the github.

https://github.com/xoco70/kendo-tournaments

Hope it helps!

$\endgroup$
  • 1
    $\begingroup$ Can you perhaps summarize the algorithm? $\endgroup$ – Yuval Filmus Aug 24 '17 at 11:17

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.