Tournament bracket placement algorithm

Question

Given a list of opponent seeds (for example seeds 1 to 16), I'm trying to write an algorithm that will result in the top seed playing the lowest seed in that round, the 2nd seed playing the 2nd-lowest seed, etc.

Grouping 1 and 16, 2 and 15, etc. into "matches" is fairly easy, but I also need to make sure that the higher seed will play the lower seed in subsequent rounds.

An example bracket with the correct placement:

1 vs 16
            1 vs 8
8 vs 9
                        1 vs 4
4 vs 13
            4 vs 5
5 vs 12
                                    1 vs 2
2 vs 15
            2 vs 7
7 vs 10
                        2 vs 3
3 vs 14
            3 vs 6
6 vs 11

As you can see, seed 1 and 2 only meet up in the final.

Answer 1

I've come up with the following algorithm. It may not be super-efficient, but I don't think that it really needs to be. It's written in PHP.

<?php
    $players = range(1, 32);
    $count = count($players);
    $numberOfRounds = log($count / 2, 2);

    // Order players.
    for ($i = 0; $i < $numberOfRounds; $i++) {
        $out = array();
        $splice = pow(2, $i); 

        while (count($players) > 0) {

            $out = array_merge($out, array_splice($players, 0, $splice));
            $out = array_merge($out, array_splice($players, -$splice));

        }            

        $players = $out;
    }

    // Print match list.
    for ($i = 0; $i < $count; $i++) {
        printf('%s vs %s<br />%s', $players[$i], $players[++$i], PHP_EOL);
    }
?>

Answer 2

With your assumptions, players 1 and 2 will play in the final, players 1-4 in the semifinals, players 1-8 in the quarterfinals and so on, so you can build the tournament recursively backwards from the final as AakashM proposed. Think of the tournament as a tree whose root is the final.

In the root node, your players are {1, 2}.

To expand the tree recursively to the next level, take all the nodes on the bottom layer in the tree, one by one, and create two children for them each, and place one of the players of the original node to each one of the child nodes created. Then add the next layer of players and map them to the game so that the worst newly added player plays against the best pre-existing player and so on.

Here first rounds of the algorithm:

 {1,2}  --- create next layer

       {1, _}
      /         --- now fill the empty slots
 {1,2}
      \{2, _}

       {1, 4}   --- the slots filled in reverse order
      /         
 {1,2}
      \{2, 3}   --- create next layer again


             /{1, _}
       {1, 4}
      /      \{4, _}
 {1,2}                  --- again fill
      \      /{2, _}
       {2, 3}
             \{3, _}

             /{1, 8}
       {1, 4}
      /      \{4, 5}    --- ... and so on
 {1,2}
      \      /{2, 7}
       {2, 3}
             \{3, 6}

As you can see, it produces the same tree you posted.

Answer 3

• At each round sort teams by seeding criteria
• (If there are n teams in a round)team at ith position plays with team n-i+1

Answer 4

# Here's one in python - it uses nested list comprehension to be succinct:

from math import log, ceil

def seed( n ):
    """ returns list of n in standard tournament seed order

    Note that n need not be a power of 2 - 'byes' are returned as zero
    """

    ol = [1]

    for i in range( ceil( log(n) / log(2) ) ):

        l = 2*len(ol) + 1

        ol = [e if e <= n else 0 for s in [[el, l-el] for el in ol] for e in s]

    return ol

Answer 5

The answer depends a bit on other variables. This is my approach to the problem. It only addresses the first bit of creating the brackets. The other logic of the bracket getting smaller is up to the reader.

• You need to know the draw size, with a minimum of 8
• You need a minimum of half the draw size in players, eg draw of 8 has a minimum of 4 players.
• You have seeded and optionally unseeded, wildcards or qualifiers in your player population.

1. Add up all the player groups and see if the player count equals the draw size. If the player group size is less than the draw size, you'll need to add "Byes".

2. In case of Byes, you'll need to assign the Byes to the (highest) seeded player(s). This results in your first couple of seeded matches (assuming you have seeded players).

   a. It could be that you have less seeded players than Byes in a draw but you do have unseeded, wildcards or qualifiers. These can be granted the remainding Byes. I treat these cases as seeded players. You can treat qualifiers or wild cards as seeded players depending on your wishes. But I find a bracket with qualifiers, wildcards and byes odd.

3. If you have unseeded players, wildcards or qualifiers, create matches vs the seeded players and append this to your seeded matches.

4. If you don't have unseeded players, wildcards or qualifiers you'll need to split your seeded player group in half. Assuming you have 8 seeds, you'll have to groups: 1-4, 5-8. You'll need to reverse the order of the second group. You now need to create matches for the remainder of the seeds. This concludes the seeded matches.

5. To create the brackets you have to split the seeded matches in half to a left and a right side. The left side has the #1 seed in it, the right side has the #2 seed in it, the #3 seed goes into left and #4 seed into right, etc. The right side also holds one seed or more with an unequal amount of seeds. Unless you only have one seed, this one stays on the left side.

6. It would be best if you shuffled the brackets (both left and right) a bit to ensure that the no 1 seed doesn't play the no 3 seed one round later in a draw size of 16 and up.

   a. You create two arrays (foo and bar) for a bracket.

   b. While you loop over each bracket, the first match and last match go into foo and the second and second to last match into bar.

   c. If you prefer your seeds to play against the worst seeded players, you must split the bracket in half, reverse both sides, and merge them again. You can omit this action if you allow a more or less equal difference between seeds.

   d. Now you need to reverse the bar and merge bar into foo, this has now become your bracket.

7. You create matches with the remainder of the unseeded players, the wildcards and the qualifiers as unseeded matches.

8. Complete the final brackets you need to determine which side has the fewest entries to start adding the first unseeded match to. This requires the following logic (assuming 0-based arrays).

   a. The index to place something in the matches is 1. Depending on the side you are working on, you'll want to add the first match as the opponent of the #1 or #2 seed. If the array is empty, just push it to the array.

   b. Every second interation you flip the index by multiplying it with -1, this means in most languages that you'll add it before the last element of the array.

   c. To make sure you have equal spacing between all the seeded players you'll need to do the following things at every second iteration:

   • Update the index by 2 when the index is more than 0.
   • Reset the index to 1 if the index is greater than half the size of one of the brackets.

Answer 6

For JavaScript code, use one of the two functions below. The former embodies imperative style & is much faster. The latter is recursive & neater, but only applicable to relatively small number of teams (<16384).

// imperative style
function foo(n) {
  const arr = new Array(n)
  arr[0] = 0
  for (let i = n >> 1, m = 1; i >= 1; i >>= 1, m = (m << 1) + 1) {
    for (let j = n - i; j > 0; j -= i) {
      arr[j] = m - arr[j -= i]
    }
  }
  return arr
}

Here you fill in the spots one by one by mirroring already occupied ones. For example, the first-seeded team (that is number 0) goes to the topmost spot. The second one (1) occupies the opposite spot in the other half of the bracket. The third team (2) mirrors 1 in their half of the bracket & so on. Despite the nested loops, the algorithm has a linear time complexity depending on the number of teams.

Here is the recursive method:

// functional style
const foo = n =>
  n === 1 ? [0] : foo(n >> 1).reduce((p, c) => [...p, c, n - c - 1], [])

Basically, you do the same mirroring as in the previous function, but recursively:

• For n = 1 team, it's just [0].

• For n = 2 teams, you apply this function to the argument n-1 (that is, 1) & get [0]. Then you double the array by inserting mirrored elements between them at even positions. Thus, [0] becomes [0, 1].

• For n = 4 teams, you do the same operation, so [0, 1] becomes [0, 3, 1, 2].

If you want to get human-readable output, increase each element of the resulting array by one:

const readableArr = arr.map(i => i + 1)

Answer 7

Since this comes up when searching on the subject, and it's hopeless to find another answer that solves the problem AND puts the seeds in a "prettier" order, I will add my version of the PHP code from darkangel. I also added the possibility to give byes to the higher seed players.

This was coded in an OO environment, so the number of participants are in $this->finalists and the number of byes are in $this->byes. I have only tested the code without byes and with two byes.

  public function getBracket() {
      $players = range(1, $this->finalists);
      for ($i = 0; $i < log($this->finalists / 2, 2); $i++) {
        $out = array();
        $reverse = false;
        foreach ($players as $player) {
          $splice = pow(2, $i);
          if ($reverse) {
            $out = array_merge($out, array_splice($players, -$splice));
            $out = array_merge($out, array_splice($players, 0, $splice));
            $reverse = false;
          } else {
            $out = array_merge($out, array_splice($players, 0, $splice));
            $out = array_merge($out, array_splice($players, -$splice));
            $reverse = true;
          }
        }
        $players = $out;
      }
      if ($this->byes) {
        for ($i = 0; $i < $this->byes; $i++ ) {
          for ($j = (($this->finalists / pow(2, $i)) - 1); $j > 0; $j--) {
            $newPlace = ($this->finalists / pow(2, $i)) - 1;
            if ($players[$j] > ($this->finalists / (pow(2 ,($i + 1))))) {
              $player = $players[$j];
              unset($players[$j]);
              array_splice($players, $newPlace, 0, $player);
            }
          }
        }
        for ($i = 0; $i < $this->finalists / (pow(2, $this->byes)); $i++ ) {
          $swap[] = $players[$i];
        }
        for ($i = 0; $i < $this->finalists /(pow(2, $this->byes)); $i++ ) {
          $players[$i] = $swap[count($swap) - 1 - $i];
        }
        return array_reverse($players);
      }
      return $players;
    }

Answer 8

This JavaScript returns an array where each even index plays the next odd index

function seeding(numPlayers){
  var rounds = Math.log(numPlayers)/Math.log(2)-1;
  var pls = [1,2];
  for(var i=0;i<rounds;i++){
    pls = nextLayer(pls);
  }
  return pls;
  function nextLayer(pls){
    var out=[];
    var length = pls.length*2+1;
    pls.forEach(function(d){
      out.push(d);
      out.push(length-d);
    });
    return out;
  }
}

> seeding(2)
[1, 2]
> seeding(4)
[1, 4, 2, 3]
> seeding(8)
[1, 8, 4, 5, 2, 7, 3, 6]
> seeding(16)
[1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11]

Answer 9

A C version.

int * pctournamentSeedArray(int PlayerCnt)
{
    int * Array;
    int * PrevArray;
    int i;

    Array = meAlloc(sizeof(int) * PlayerCnt);

    if (PlayerCnt == 2)
    {
        Array[0] = 0;
        Array[1] = 1;
        return Array;
    }

    PrevArray = pctournamentSeedArray(PlayerCnt / 2);
    for (i = 0; i < PlayerCnt;i += 2)
    {
        Array[i] = PrevArray[i / 2];
        Array[i + 1] = (PlayerCnt - 1) - Array[i] ;
    }
    meFree(PrevArray);
    return Array;
}

Answer 10

Old issue but i ran across it while researching this problem. Based on the general algorithm from AakashM and Antti Huima, here is what i ended up with in c#. I'm sure its not the most computationally effective but i wrote it to be easy to follow (for my self) and easily portable

Besides creating the brackets, it also sets a Round value and a Seed value, to make sorting easier, i needed the seed as an explicit value to store in the database and not have to rely on id order. Participants are expected to be sorted by rank but they dont have to be. If the number of participants is not a multiple of two it will create bye brackets (where excess teams have no opponent).

To create a tournament of a fixed size like a 64 bracket tournament with less than 32 players you can just let the main while loop run longer, this will create additional empty brackets.

Hopefully someone finds this helpful!

var participants = Enumerable.Range(1, 64).Select(s => (long)s).ToList();
var brackets = GenerateBrackets(participants);

static List<Bracket> GenerateBrackets(List<long> participants)
{
    var totalRounds = 1;
    int participantIndex = 0;
    var finalBracket = new Bracket
    {
        Red = participants.ElementAtOrDefault(participantIndex++),
        Blue = participants.ElementAtOrDefault(participantIndex++),
    };
    var currentRound = new List<Bracket>();
    var previousRound = new List<Bracket> { finalBracket };

    while (participantIndex < participants.Count)
    {
        totalRounds++;
        currentRound.Clear();

        foreach (var bracket in previousRound)
        {
            bracket.RedParentBracket = new Bracket
            {
                ChildBracket = bracket,
                Red = bracket.Red
            };

            bracket.BlueParentBracket = new Bracket
            {
                ChildBracket = bracket,
                Red = bracket.Blue
            };

            currentRound.Add(bracket.RedParentBracket);
            currentRound.Add(bracket.BlueParentBracket);
        }

        foreach (var newBracket in currentRound.OrderByDescending(b => participants.IndexOf(b.Red)))
            newBracket.Blue = participants.ElementAtOrDefault(participantIndex++);

        previousRound.Clear();
        previousRound.AddRange(currentRound);
    }

    finalBracket.Round = totalRounds;
    SetDepthOnParents(finalBracket);

    var orderedBrackets = new List<Bracket>();
    for (var i = 1; i <= finalBracket.Round; i++)
        OrderBracketsInRoundBySeed(finalBracket, i, orderedBrackets);

    for (int i = 0; i < orderedBrackets.Count; i++)
        orderedBrackets[i].Seed = i + 1;

    return orderedBrackets;
}

static void OrderBracketsInRoundBySeed(Bracket bracket, int round, List<Bracket> brackets)
{
    if (bracket == null)
        return;
    else if (bracket.Round == round)
        brackets.Add(bracket);
    else
    {
        OrderBracketsInRoundBySeed(bracket.RedParentBracket, round, brackets);
        OrderBracketsInRoundBySeed(bracket.BlueParentBracket, round, brackets);
    }
}

static void SetDepthOnParents(Bracket bracket)
{
    if (bracket == null)
        return;

    if (bracket.RedParentBracket != null)
    {
        bracket.RedParentBracket.Round = bracket.Round - 1;
        SetDepthOnParents(bracket.RedParentBracket);
    }
    if (bracket.BlueParentBracket != null)
    {
        bracket.BlueParentBracket.Round = bracket.Round - 1;
        SetDepthOnParents(bracket.BlueParentBracket);
    }
}

public class Bracket
{
    public long Red { get; set; }
    public long Blue { get; set; }
    public int Round { get; set; }
    public int Seed { get; set; }

    public Bracket ChildBracket { get; set; }
    public Bracket RedParentBracket { get; set; }
    public Bracket BlueParentBracket { get; set; }
}

Answer 11

I also wrote a solution written in PHP. I saw Patrik Bodin's answer, but thought there must be an easier way.

It does what darkangel asked for: It returns all seeds in the correct positions. The matches are the same as in his example, but in a prettier order, seed 1 and seed number 16 are on the outside of the schema (as you see in tennis tournaments).

If there are no upsets (meaning a higher seeded player always wins from a lower seeded player), you will end up with seed 1 vs seed 2 in the final.

It actually does two things more:

1. It shows the correct order (which is a requirement for putting byes in the correct positions)

2. It fills in byes in the correct positions (if required)

A perfect explanation about what a single elimination bracket should look like: http://blog.playdriven.com/2011/articles/the-not-so-simple-single-elimination-advantage-seeding/

Code example for 16 participants:

<?php

define('NUMBER_OF_PARTICIPANTS', 16);

$participants = range(1,NUMBER_OF_PARTICIPANTS);
$bracket = getBracket($participants);
var_dump($bracket);

function getBracket($participants)
{
    $participantsCount = count($participants);  
    $rounds = ceil(log($participantsCount)/log(2));
    $bracketSize = pow(2, $rounds);
    $requiredByes = $bracketSize - $participantsCount;

    echo sprintf('Number of participants: %d<br/>%s', $participantsCount, PHP_EOL);
    echo sprintf('Number of rounds: %d<br/>%s', $rounds, PHP_EOL);
    echo sprintf('Bracket size: %d<br/>%s', $bracketSize, PHP_EOL);
    echo sprintf('Required number of byes: %d<br/>%s', $requiredByes, PHP_EOL);    

    if($participantsCount < 2)
    {
        return array();
    }

    $matches = array(array(1,2));

    for($round=1; $round < $rounds; $round++)
    {
        $roundMatches = array();
        $sum = pow(2, $round + 1) + 1;
        foreach($matches as $match)
        {
            $home = changeIntoBye($match[0], $participantsCount);
            $away = changeIntoBye($sum - $match[0], $participantsCount);
            $roundMatches[] = array($home, $away);
            $home = changeIntoBye($sum - $match[1], $participantsCount);
            $away = changeIntoBye($match[1], $participantsCount);
            $roundMatches[] = array($home, $away);
        }
        $matches = $roundMatches;
    }

    return $matches;

}

function changeIntoBye($seed, $participantsCount)
{
    //return $seed <= $participantsCount ?  $seed : sprintf('%d (= bye)', $seed);  
    return $seed <= $participantsCount ?  $seed : null;
}

?>

The output:

Number of participants: 16
Number of rounds: 4
Bracket size: 16
Required number of byes: 0
C:\projects\draw\draw.php:7:
array (size=8)
  0 => 
    array (size=2)
      0 => int 1
      1 => int 16
  1 => 
    array (size=2)
      0 => int 9
      1 => int 8
  2 => 
    array (size=2)
      0 => int 5
      1 => int 12
  3 => 
    array (size=2)
      0 => int 13
      1 => int 4
  4 => 
    array (size=2)
      0 => int 3
      1 => int 14
  5 => 
    array (size=2)
      0 => int 11
      1 => int 6
  6 => 
    array (size=2)
      0 => int 7
      1 => int 10
  7 => 
    array (size=2)
      0 => int 15
      1 => int 2

If you change 16 into 6 you get:

Number of participants: 6
Number of rounds: 3
Bracket size: 8
Required number of byes: 2
C:\projects\draw\draw.php:7:
array (size=4)
  0 => 
    array (size=2)
      0 => int 1
      1 => null
  1 => 
    array (size=2)
      0 => int 5
      1 => int 4
  2 => 
    array (size=2)
      0 => int 3
      1 => int 6
  3 => 
    array (size=2)
      0 => null
      1 => int 2

Answer 12

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!