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
