sorting tournament seeds

I'm making a HTML/JS powered single/double elimination bracket web app. I am struggling to figure out how to assign the first round matches from a list of seeded teams/players. For example, in a bracket of 8 players the first round matches are:

1v8 4v5 2v7 3v6

In more generic terms, the seeds can be thought of as an array(as I assign teams to matches by popping them off an array): 1,2,3,4,5,6,7,8

which needs to be sorted to: 1,8,4,5,2,7,3,6

To clarify, the higher seeds need to have the maximum distance between them in the sorted array, this is so that in a bracket with no upsets, lower seeds get knocked out first and and matches with high seeds occur as late as possible. In practical terms, think of a tennis tournament, where you want to prevent the top 4 players in a bracket of 16 or 32 etc from playing each other until the semi finals. So, the correct array output for a 16 seed bracket is:

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

which translates to the follo开发者_JAVA技巧wing 1st round matches:

1v16 8v9 4v13 5v12 2v15 7v10 3v14 6v11

Thanks to Matt Ball for the correct algorithm for an 8 seed bracket

---

The ideas of matching players from the top and bottom is correct but not quite complete. Doing it once works great for the first round:

while (seeds.length)
{
    firstRound.push(seeds.shift());
    firstRound.push(seeds.pop());
}
1, 2, 3, 4, 5, 6, 7, 8 => 1, 8, 2, 7, 3, 6, 4, 5

...but in the second round, seed 1 meets seed 2 and 3 meets 4. We need to do the first/last shuffle for each round. First time through, we move each element individually. Second time through, we move each PAIR of elements. Third time through we move groups of four, etc, until our group size is seeds.length/2. Like so:

// this is ruby, aka javascript psuedo-code :)

bracket_list = seeds.clone

slice = 1
while slice < bracket_list.length/2
  temp = bracket_list
  bracket_list = []

  while temp.length > 0
    bracket_list.concat temp.slice!(0, slice)       # n from the beginning
    bracket_list.concat temp.slice!(-slice, slice)  # n from the end
  end

  slice *= 2
end
return bracket_list

Here's what the array will look like as you go through the iterations (parenthesis indicate the increasing group size):

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

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

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

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

So now, after the bottom 8 players are eliminated, we're left with 1, 8, 4, 5, 2, 7, 3, 6. After the bottom 4 are eliminated from there we have 1, 4, 2, 3, and in the final round just 1, 2.

It's hard to explain this without being able to draw a bracket... Let me know if I can clarify something for you.

---

I wrote a solution in PHP (see https://stackoverflow.com/a/45566890/760777). Here is the javascript version.

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 8 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 8 participants:

var NUMBER_OF_PARTICIPANTS = 8; // Set the number of participants

if (!String.prototype.format) {
  String.prototype.format = function() {
    var args = arguments;
    return this.replace(/{(\d+)}/g, function(match, number) { 
      return typeof args[number] != 'undefined' ? args[number] : match;
    });
  };
}

var participants = Array.from({length: NUMBER_OF_PARTICIPANTS}, (v, k) => k + 1) ;
var bracket = getBracket(participants);

console.log(bracket);

function getBracket(participants)
{
  var participantsCount = participants.length;	
  var rounds = Math.ceil(Math.log(participantsCount)/Math.log(2));
  var bracketSize = Math.pow(2, rounds);
  var requiredByes = bracketSize - participantsCount;
	
  console.log("Number of participants: {0}".format(participantsCount));
  console.log("Number of rounds: {0}".format(rounds));
  console.log("Bracket size: {0}".format(bracketSize));
  console.log("Required number of byes: {0}".format(requiredByes));    
    
  if(participantsCount < 2) {
    return [];
  }
    
  var matches = [[1,2]];
  
  for(var round = 1; round < rounds; round++) {
    var roundMatches = [];
    var sum = Math.pow(2, round + 1) + 1;
    
    for(var i = 0; i < matches.length; i++) {
      var home = changeIntoBye(matches[i][0], participantsCount);
      var away = changeIntoBye(sum - matches[i][0], participantsCount);
      roundMatches.push([home, away]);
      home = changeIntoBye(sum - matches[i][1], participantsCount);
      away = changeIntoBye(matches[i][1], participantsCount);
      roundMatches.push([home, away]);
    }
    matches = roundMatches;   
    
  }   
  
  return matches;    
}

function changeIntoBye(seed, participantsCount)
{
    //return seed <= participantsCount ?  seed : '{0} (= bye)'.format(seed);  
    return seed <= participantsCount ?  seed : null;
}

Change NUMBER_OF_PARTICIPANTS from 8 to 6 to get two byes.

Good luck. RWC

---

This is probably not as efficient as @alex's answer using a custom sort function, but certainly easier to write and understand:

// This algorithm assumes that seeds.length is an even number
var seeds = [1, 2, 3, 4, 5, 6, 7, 8],
    firstRound = [];

while (seeds.length)
{
    firstRound.push(seeds.shift());
    firstRound.push(seeds.pop());
}

// seeds is now empty
// firstRound is now [1, 8, 2, 7, 3, 6, 4, 5]

Demo 1

---

Actually, I just thought of a faster algorithm (in-place "sorting", takes O(n) time):

// Also assumes that seeds.length is an even number
var seeds = [1, 2, 3, 4, 5, 6, 7, 8],
    numSeeds = seeds.length,
    stop = numSeeds >> 1,
    temp;

for (var i=1; i<stop; i=i+2)
{
    temp = seeds[i];
    seeds[i] = seeds[numSeeds-i];
    seeds[numSeeds-i] = temp;
}

// seeds is now [1, 8, 3, 6, 5, 4, 7, 2]

Demo 2

Note that neither of these algorithms generates exactly the same order of pairs as in the OP, but they both generate the same set of pairs:

• (1,8)
• (2,7)
• (3,6)
• (4,5)

---

I've come up with a solution, but it's outside the scope of just "sorting arrays".

The (javascript) code is at http://jsbin.com/ukomo5/2/edit.

In basic terms, the algorithm assumes that no upsets will occur in the bracket, therefore seeds 1 and 2 should meet in the final round. It iterates through each seed in each round (starting from the pre-calculated grand final, working backwards), calculating the unknown seed in the match in the previous round that the current seed (in the iteration) had won. This can be done because given a seed and round number, you can work out what the other seed should be:

other seed = number of seeds in round + 1 - the known seed

To illustrate, in the semifinals:

Semifinal 1 (where known seed is 1): other seed = 4 + 1 - 1 = 4

Semifinal 2 (where known seed is 2): other seed = 4 + 1 - 2 = 3

I just noticed this pattern when looking at a "no upsets" bracket I had drawn.

In the final iteration (ie round 1) all seeds and their position are known, ready to be assigned to matches. The correct sorted array is below:

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

Thanks again to Matt Ball who came up with a correct solution for small brackets (It's difficult to state the problem and desired solution without detailed context, which I didn't do completely in my initial question).

If anyone has another solution or a more elegant version of my solution let us know!

---

Here's the algorithm I've developed. Step 1 is to draw a table with as many rows as there are teams (rounded up to a power of 2) and as many columns as needed to represent the number of teams in binary. Say, there are 8 teams. The table will initially look like this (the dots represent horizontal cell borders):

. . . | | | | . . . | | | | . . . | | | | . . . | | | | . . . | | | | . . . | | | | . . . | | | | . . . | | | | . . .

Columns are numbered from the left in ascending order. For each column put an asterisk at every 2^(column number) row. That is, every 2nd row in column 1, every 4th row in column 2 etc.

. . . | | | | . . . | | | | * . . | | | | . . . | | | | * * . | | | | . . . | | | | * . . | | | | . . . | | | |

---

Start with a 0 in each column in the 1st row. Thereafter, for successive rows in each column toggle from 0-1 and 1-0 unless there is an asterisk in that row. This is the result:

. . . |0|0|0| . . . |1|1|1| * . . |1|0|0| . . . |0|1|1| * * . |0|1|0| . . . |1|0|1| * . . |1|1|0| . . . |0|0|1|

---

The last step is to evaluate each row treating the string of 0's and 1's as a binary number. This will result in values from 0-7. Adding 1 to each results in values from 1-8. These correspond to the seedings.

. . . |0|0|0| + 1 = 1 . . . |1|1|1| + 1 = 8 * . . |1|0|0| + 1 = 5 . . . |0|1|1| + 1 = 4 * * . |0|1|0| + 1 = 3 . . . |1|0|1| + 1 = 6 * . . |1|1|0| + 1 = 7 . . . |0|0|1| + 1 = 2

---

Each pair of seeds are the matches to be played in order. ie. 1-8, 5-4, 3-6 and 7-2. This is extendable to any number of seeds. When byes are to be inserted due to the number of entries being less than a power of 2, they take the highest seed values. eg. if there were only 28 entries then byes take the positions assigned to 29, 30, 31 and 32.

---

I was really intrigued and impressed with Cliff's algorithm here. I think it is very clever. Here is a simple implementation I wrote in ruby. The BYEs are returned as -1.

def seed(n)
  rounded_n = next_power_of_two(n)
  nbr_bits_required=rounded_n.to_s(2).length-1
  binary_seeds = Array.new(rounded_n) {Array.new(nbr_bits_required)}
  binary_seeds[0]=Array.new(nbr_bits_required){0}

  nbr_bits_required.times do |col|    
    1.upto(rounded_n-1) do |row|
      if row % (2**(col+1)) == 0
        #asterisk in the previous row, don't inverse the bit
        binary_seeds[row][col] = binary_seeds[row-1][col]
      else
        #no asterisk in the previous row, inverse the bit
        binary_seeds[row][col] = binary_seeds[row-1][col] == 0 ? 1 : 0
      end
    end
  end

  #output the result in decimal format
  binary_seeds.collect {|bs| s=(bs.join("")).to_i(2)+1; s>n ? -1 : s}
end

def next_power_of_two(n)
  k = 1
  k*=2 while k<n
  k
end

Test it out:

seed(8)
=> [1, 8, 5, 4, 3, 6, 7, 2]

seed(6)
=> [1, -1, 5, 4, 3, 6, -1, 2]

---

I wrote an implementation of Cliff's algorithm in Elixir.

It is not extremely efficient but it is very clear. I have also included some unit tests to validate it.

defmodule Seeding do
  @moduledoc """
  https://stackoverflow.com/questions/8355264/tournament-bracket-placement-algorithm
  """

  @doc """
  Converts a "seeded list" to first-round pairings.

  This uses the algorithm described here:
  https://stackoverflow.com/a/20370966/13738464
  """
  def seeded_list_to_first_round_pairings(seeding_list) do
    seeding_list_count = Enum.count(seeding_list)
    desired_string_length = rounded_log2_ceil(seeding_list_count)
    mask_int_by_num_2_factors = build_mask_int_by_num_2_factors_map(desired_string_length)

    0..(Math.pow(2, desired_string_length) - 1)//1
    |> Enum.reduce([], fn
      0, [] ->
        [0]

      i, [prev_i | _] = acc ->
        num_2_factors = number_of_2_factors(i)
        mask_int = Map.get(mask_int_by_num_2_factors, num_2_factors)
        next_i = Bitwise.bxor(prev_i, mask_int)
        [next_i | acc]
    end)
    |> Enum.reverse()
    |> Enum.chunk_every(2)
    |> Enum.map(fn pair ->
      pair
      |> Enum.reject(&(&1 >= seeding_list_count))
      |> Enum.map(&Enum.at(seeding_list, &1))
    end)
  end

  @doc """
  Returns inferred seeded list, given first-round pairings
  """
  def first_round_pairings_to_seeded_list(first_round_pairings) do
    seeded_elements = List.flatten(first_round_pairings)

    seeded_indexes =
      0..(Enum.count(seeded_elements) - 1)
      |> seeded_list_to_first_round_pairings()
      |> List.flatten()

    Enum.zip(seeded_elements, seeded_indexes)
    |> Enum.sort_by(fn {_element, index} -> index end)
    |> Enum.map(fn {element, _index} -> element end)
  end

  defp rounded_log2_ceil(number) do
    number
    |> Math.log2()
    |> Float.ceil()
    |> Float.to_string()
    |> Integer.parse()
    |> elem(0)
  end

  defp build_mask_int_by_num_2_factors_map(desired_string_length) do
    Enum.reduce(
      0..(desired_string_length - 1)//1,
      %{},
      fn num_2_factors, acc ->
        mask_int =
          bxor_mask_int(
            num_2_factors,
            desired_string_length
          )

        Map.put(acc, num_2_factors, mask_int)
      end
    )
  end

  defp bxor_mask_int(number_of_2_factors, desired_string_length) do
    bit_string =
      Enum.map_join(
        1..desired_string_length,
        &if(&1 <= number_of_2_factors, do: 0, else: 1)
      )

    {mask_integer, ""} = Integer.parse(bit_string, 2)
    mask_integer
  end

  @doc """
  Returns the number of "2" factors of the given integer.

  Every integer can be expressed as the "product of irreducible factors".
  For example:
  16 = 2 * 2 * 2 * 2
  12 = 2 * 2 * 3
  17 = 17 (prime)
  """
  @spec number_of_2_factors(non_neg_integer()) :: non_neg_integer()
  def number_of_2_factors(int) when int < 2, do: 0
  def number_of_2_factors(2), do: 1
  def number_of_2_factors(4), do: 2
  def number_of_2_factors(8), do: 3
  def number_of_2_factors(16), do: 4
  def number_of_2_factors(32), do: 5
  def number_of_2_factors(int), do: get_2_factor_count(int, 0)

  @spec get_2_factor_count(non_neg_integer(), non_neg_integer()) :: non_neg_integer()
  defp get_2_factor_count(int, result) do
    if rem(int, 2) == 0 and int > 0 do
      int
      |> div(2)
      |> get_2_factor_count(result + 1)
    else
      result
    end
  end
end

the tests:

defmodule SeedingTest do
  use ExUnit.Case

  describe "seeded_list_to_first_round_pairings/1" do
    test "shuffles a seeding list into first-round pairings" do
      for {input, output} <- [
            {1..6, [[1], [5, 4], [3, 6], [2]]},
            {1..7, [[1], [5, 4], [3, 6], [7, 2]]},
            {1..8, [[1, 8], [5, 4], [3, 6], [7, 2]]},
            {1..9, [[1], [9, 8], [5], [4], [3], [6], [7], [2]]},
            {1..64,
             [
               [1, 64],
               [33, 32],
               [17, 48],
               [49, 16],
               [9, 56],
               [41, 24],
               [25, 40],
               [57, 8],
               [5, 60],
               [37, 28],
               [21, 44],
               [53, 12],
               [13, 52],
               [45, 20],
               [29, 36],
               [61, 4],
               [3, 62],
               [35, 30],
               [19, 46],
               [51, 14],
               [11, 54],
               [43, 22],
               [27, 38],
               [59, 6],
               [7, 58],
               [39, 26],
               [23, 42],
               [55, 10],
               [15, 50],
               [47, 18],
               [31, 34],
               [63, 2]
             ]}
          ] do
        assert Seeding.seeded_list_to_first_round_pairings(input) == output
      end
    end
  end

  describe "first_round_pairings_to_seeded_list/1" do
    test "returns the seeded list assumed to create the given first-round pairings" do
      for {input, output} <- [
            {[[1, 8], [5, 4], [3, 6], [7, 2]], Enum.to_list(1..8)},
            {[[1, 9], [8], [5], [4], [3], [6], [7], [2]], Enum.to_list(1..9)}
          ] do
        assert Seeding.first_round_pairings_to_seeded_list(input) == output
      end
    end
  end
end