Алгоритм размещения 32 сеяных игроков в турнире на 128 человек

Описание базового алгоритма:

Предположим, вы хотите посеять 4 игроков в турнире из 8 игроков.

        [ ][ ][ ][ ][ ][ ][ ][ ]    8 empty positions

Посеять первого игрока легко, на самом деле не имеет значения, куда мы его поместим. Мы поместили его в начало, чтобы упростить алгоритм.

        [1][ ][ ][ ][ ][ ][ ][ ]

Если мы хотим засеять второго игрока, нам нужно разделить все поле на две части. Игрок, который находится в левой части, встретится с игроком справа только в финале. Поэтому второй игрок должен быть помещен в правую часть, чтобы два лучших игрока не встретились до финального матча. Снова ставим игрока в начало его части.

      [1][ ][ ][ ]    [2][ ][ ][ ]

Теперь мы снова разделяем эти две части и помещаем третьего и четвертого игрока в новые пустые части. Теперь третий игрок в полуфинале встретится с первым игроком.

[1][ ]    [3][ ]        [2][ ]    [4][ ]

Обратите внимание, что алгоритм размещает нечетные числа в левой части, а четные - в правой. Пустые ячейки теперь могут быть заполнены случайными игроками. Этот алгоритм в основном тот же, что предложил @Nico Schertler.

Программирование:

Моя идея состояла в том, чтобы определить функцию, которая принимает позицию игрока (например, 1,2,3,4 и так далее) и количество свободных позиций (в вашем примере 128) и возвращает, где вы должны разместить этого игрока. Я написал функцию на Java, но ее будет легко адаптировать.

/**
 * @param rank
 *            rank of the player, best player == 1, second best player == 2
 * @param partSize
 *            number of total free positions. Has to be a power of 2 (e.g.
 *            2,4,8,16,32)
 * @return returns the start position of the player, zero based
 */
public static int seedPlayer(int rank, int partSize) {
    // base case, if rank == 1, return position 0
    if (rank <= 1) {
        return 0;
    }

    // if our rank is even we need to put the player into the right part
    // so we add half the part size to his position
    // and make a recursive call with half the rank and half the part size
    if (rank % 2 == 0) {
        return partSize / 2 + seedPlayer(rank / 2, partSize / 2);
    }

    // if the rank is uneven, we put the player in the left part
    // since rank is uneven we need to add + 1 so that it stays uneven
    return seedPlayer(rank / 2 + 1, partSize / 2);
}

Пример:

Давайте посеем наш первый турнир (8 посеянных игроков, всего 8 игроков)

for (int i = 1; i <= 8; i++) {
    System.out.printf("seeded player %d in position %d%n", i, seedPlayer(i, 8) + 1);
}

Это печатает:

seeded player 1 in position 1
seeded player 2 in position 5
seeded player 3 in position 3
seeded player 4 in position 7
seeded player 5 in position 2
seeded player 6 in position 6
seeded player 7 in position 4
seeded player 8 in position 8

в результате в этом поле:

[1][5][3][7][2][6][4][8] Perfect! Like expected!

Дальнейшее примечание:

Я бы не стал набирать более 25% игроков, чтобы турнир со временем изменился, и каждый не очень хороший игрок получил шанс сыграть против разных игроков.

Я могу думать о двух подходах:

1. Ответ Absurd-Mind и добавление к нему дополнительной информации.

Нам не только нужно разделить два верхних семени, чтобы избежать их встречи где-либо до финального раунда, поместив их в две отдельные половины, мы должны убедиться, что игрок с лучшим сеянием может сыграть с последним сеяным игроком в первом раунде, второй сеяный игрок играет вторым последним и так далее.

Алгоритм, предложенный Absurd-Mind, на самом деле заботится об этом. Если бы мне пришлось что-то менять, это было бы только в последней функции seedPlayer. Или я бы просто добавил еще один шаг, извлекающий крайности с обеих сторон его результата, чтобы поместить их в другой массив, чтобы получить позиции массива, как указано в вопросе.

For n=8, 
[1][5][3][7][2][6][4][8] \\previous result

\\extracting the extreme values on either side and placing them in another array:
[1][8] [5][4] [3][6] [7][2]

\\next round (assuming the higher seed wins):
[1][4] [3][2]

\\final round:
[1][2]

Hence, the order obtained initially is correct

2. Соблюдайте закономерность

Нет конкретной формулы для получения n-го члена ряда (по крайней мере, я не смог его найти). Но есть скрытая закономерность, которую можно использовать. Схема вырисовывается, когда вы пишете раздачу таким образом:

(Arrowhead indicates the direction of the ascending order)
For n=2,
1 ---> 2

For n=4,
1 ---> 2
4 <--- 3

For n=8,
1 ---> 2
4 <--- 3
5 ---> 6
8 <--- 7

In general,
m ---> m+1
....
....
n <--- n-1

Сначала разделите количество участников (или игроков) на 2. Предположим для удобства два массива X и Y (каждый размером n / 2). Записи с одной стороны стрелок должны храниться в массиве X, а другая половина - в массиве Y.

1. Enter n (number of players, should be a power of 2)
2. Arrays X[n/2], Y[n/2]
   Integer a=1
3. for (i=1, i<=n/4, i++)
       {
       if(i=1){
         X[i]=a;
         Y[i]=a+1;}
       else if (i%2=0) {  \\if i is even
         X[i]=2i;
         Y[i]=X[i]-1;}
       else {
         X[i]=2i-1;
         Y[i]=X[i]+1; }
       a++;
       }

Resulting arrays (for n=16):
X=[1][4][5][8][9][12][13][16]
Y=[2][3][6][7][10][11][14][15]

Теперь мы разделили два верхних семени на две отдельные половинки. Мы также соответственно разделили другие посевы, чтобы избежать нечестного противостояния в предыдущих раундах. Теперь я бы написал еще один шаг, чтобы извлечь крайности в каждом массиве и разместить их в следующем порядке

X= *[1]* [4][5][8][9][12][13] *[16]*
X= *[4]* [5][8][9][12] *[13]* 
and so on...

Мы получаем,

A=[1][16] [4][13] [5][12] [8][9]

Similarly for the other half,
B=[2][15] [3][14] [6][11] [7][10] 

Продолжайте извлекать победителя из крайностей с обеих сторон, пока не дойдете до победителя из обоих сетов A и B, которые сыграют друг с другом в финале.

Надеюсь, это поможет!

Есть формула для выбора игроков в порядке вывода.

Математика проще с подсчетом игроков на основе 0, поэтому я буду делать это, преобразовывая по мере необходимости для вывода и ввода.

Начните с начального числа игрока 0 в позиции 0.

PC = Player count (filled up with unseeded players then bye's to power of 2)
slot[0] = seeded[0]
for(n = 1; n < PC; n++) {
    seed = slot[n-(1<<ffs(n))]^(PC>>ffs(n))
    slot[n] = seeded[seed];
}

ffs - это найти первый набор, также известный как счетчик завершающих нулей. Должен возвращать 0 для установленного младшего бита .enter code here