турнир по сортировке семян

Question

Я создаю веб-приложение с одним или двумя скобками на основе HTML / JS. Я изо всех сил пытаюсь выяснить, как назначить матчи первого круга из списка отобранных команд / игроков. Например, в сетке из 8 игроков матчи первого раунда:

1v8 4v5 2v7 3V6

В более общих терминах семена можно рассматривать как массив (так как я назначаю команды для матчей, выталкивая их из массива): 1,2,3,4,5,6,7,8

, который нужно отсортировать по: 1,8,4,5,2,7,3,6

Чтобы уточнить, более высокие семена должны иметь максимальное расстояние между ними в отсортированном массиве, это так, чтобы в скобке без смещений сначала отбивались более низкие семена, а совпадения с высокими семенами происходили как можно позже. , В практическом плане, подумайте о теннисном турнире, где вы хотите помешать четырем лучшим игрокам в сетке 16 или 32 и так далее играть друг с другом до полуфинала. Таким образом, правильный вывод массива для 16 начального скобка:

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

, что означает следующие матчи 1-го раунда:

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

Спасибо Мэтту Боллу за правильный алгоритм для 8-ми семенной скобки

Answer 1

Идея подбора игроков сверху и снизу верна, но не вполне завершена. Выполнение одного раза отлично работает для первого раунда:

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

... но во втором раунде семя 1 встречается с семенем 2, а 3 встречается с 4. Нам нужно делать первый / последний случай перемешивания для каждого раунда. В первый раз мы перемещаем каждый элемент индивидуально . Во второй раз мы перемещаем каждую ПАРУ элементов. В третий раз мы перемещаем групп по четыре и т. Д., Пока размер нашей группы не станет seeds.length/2. Вот так:

// 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

Вот как будет выглядеть массив при прохождении итераций (круглые скобки указывают на увеличение размера группы):

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)

Так что теперь, после того, как 8 нижних игроков выбиты, у нас остается 1, 8, 4, 5, 2, 7, 3, 6. После того, как нижние 4 устранены оттуда, у нас есть 1, 4, 2, 3, а в последнем раунде просто 1, 2.

Трудно объяснить это, не имея возможности нарисовать скобку ... Дайте мне знать, если я смогу кое-что прояснить для вас.

Answer 2

Я придумала решение, но оно выходит за рамки просто «сортировки массивов».

(javascript) код в http://jsbin.com/ukomo5/2/edit.

В общих чертах, алгоритм предполагает, что в скобках не произойдет никаких сбоев, поэтому семена 1 и 2 должны встретиться в последнем раунде. Он перебирает каждое начальное число в каждом раунде (начиная с предварительно рассчитанного гранд-финала, работая в обратном направлении), вычисляя неизвестное начальное число в матче в предыдущем раунде, которое выиграло текущее начальное число (в итерации). Это может быть сделано, потому что, имея начальное и круглое число, вы можете определить, каким должно быть другое семя:

другое семя = количество семян в цикле + 1 - известное семя

Для иллюстрации в полуфинале:

Полуфинал 1 (где известно, что семя равно 1): другое семя = 4 + 1 - 1 = 4

Полуфинал 2 (где известно, что семя равно 2): другое семя = 4 + 1 - 2 = 3

Я только что заметил эту схему, когда смотрел на нарисованную мной скобку «без расстройств».

В последней итерации (т. Е. Раунд 1) все семена и их положение известны, они готовы к назначению на матчи. Правильный отсортированный массив ниже:

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

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

Если у кого-то есть другое решение или более элегантная версия моего решения, сообщите нам!

Answer 3

Это, вероятно, не так эффективно, как @ alex's ответ с использованием пользовательской функции sort, но, безусловно, легче написать и понять:

// 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]

Демо 1

---

На самом деле, я только что подумал о более быстром алгоритме («сортировка на месте», занимает O(n) время):

// 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]

Демо 2

Обратите внимание, что ни один из этих алгоритмов не генерирует точно такой же порядок пар, как в OP, но оба они генерируют один и тот же набор пар:

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

Answer 4

Вот алгоритм, который я разработал. Шаг 1 состоит в том, чтобы нарисовать таблицу с таким количеством строк, сколько есть команд (округленных до степени 2) и столько столбцов, сколько необходимо для представления количества команд в двоичном формате. Скажем, есть 8 команд. Изначально таблица будет выглядеть так (точки представляют горизонтальные границы ячеек):

. , , | | | | , , , | | | | , , , | | | | , , , | | | | , , , | | | | , , , | | | | , , , | | | | , , , | | | | , , .

Столбцы пронумерованы слева в порядке возрастания. Для каждого столбца ставьте звездочку в каждой строке 2 ^ (номер столбца). То есть каждая 2-я строка в столбце 1, каждая 4-я строка в столбце 2 и т. Д.

. , , | | | | , , , | | | | * , | | | | , , , | | | | * *. | | | | , , , | | | | * , | | | | , , , | | | |

---

Начните с 0 в каждом столбце в 1-й строке. После этого для последовательных строк в каждом столбце переключайтесь с 0-1 на 1-0, если в этой строке нет звездочки. Это результат:

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

---

Последний шаг - оценить каждую строку, рассматривая строку из 0 и 1 как двоичное число. Это приведет к значениям от 0 до 7. Добавление 1 к каждому приводит к значениям от 1 до 8. Они соответствуют сеянцам.

. , , | 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

---

Каждая пара семян - это совпадения, которые должны быть сыграны по порядку то есть. 1-8, 5-4, 3-6 и 7-2. Это распространяется на любое количество семян. Когда байты должны быть вставлены из-за того, что число записей меньше степени 2, они принимают самые высокие начальные значения. например. если было только 28 записей, то байсы занимают позиции, назначенные 29, 30, 31 и 32.

Answer 5

Я написал решение на PHP (см. https://stackoverflow.com/a/45566890/760777). Вот версия javascript.

Возвращает все семена в правильных позициях . Совпадения совпадают св его примере, но в порядке красивее , семя 1 и семя номер 8 находятся снаружи схемы (как вы видите в теннисных турнирах).

Если нет расстройств (это означает, что игрок с более высоким уровнем сеяний всегда выигрывает у игрока с более низким сеяным), в итоге вы получите семя 1 против семени 2.

На самом деле это делает две вещи больше:

1. Показывает правильный порядок (который является обязательным условием для размещения байтов в правильных положениях)

2. Он заполняет байсы в правильных положениях (если требуется)

Прекрасное объяснение того, как должна выглядеть одна исключающая скобка: http://blog.playdriven.com/2011/articles/the-not-so-simple-single-elimination-advantage-seeding/

Пример кода для 8 участников:

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;
}

Измените NUMBER_OF_PARTICIPANTS с 8 на 6, чтобы получить два пока.

Удачи.RWC