Алгоритм размещения турнирной сетки

Question

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

Группировать 1 и 16, 2 и 15 и т. д. в «спички» довольно легко, но мне также нужно убедиться, что старшее семя сыграет нижнее семя в последующих раундах.*

Пример кронштейна с правильным расположением:

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

Как видите, семена 1 и 2 встречаются только в финале.

Answer 1

Этот JavaScript возвращает массив, в котором каждый четный индекс воспроизводит следующий нечетный индекс

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 2

С вашими предположениями, игроки 1 и 2 будут играть в финале, игроки 1-4 в полуфинале, игроки 1-8 в четвертьфинале и так далее, так что вы можете рекурсивно строить турнир в обратном направлении из финала, как предложил AakashM , Думайте о турнире как о дереве, корнем которого является финал.

В корневом узле ваши игроки: {1, 2}.

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

Вот первые раунды алгоритма:

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

Как видите, он создает то же дерево, что и вы.

Answer 3

Я также написал решение, написанное на PHP. Я видел ответ Патрика Бодина, но подумал, что должен быть более легкий путь.

Он делает то, о чем просил даркангел: он возвращает все семена в правильных положениях . Совпадения такие же, как в его примере, но в порядке красивее семена 1 и семена 16 находятся снаружи схемы (как вы видите в теннисных турнирах).

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

На самом деле он делает еще две вещи:

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

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

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

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

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

?>

Выход:

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

Если вы измените 16 на 6, вы получите:

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 4

Я придумал следующий алгоритм. Это может быть не очень эффективно, но я не думаю, что это действительно нужно. Написано на 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 5

# 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 6

A C версия.

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 7

Я работал над плагином PHP / Laravel, который генерирует скобки с / без предварительного циклического перебора. Может быть, это может быть полезно для вас, я не знаю, какую технологию вы используете. Здесь GitHub.

https://github.com/xoco70/kendo-tournaments

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

Answer 8

Для кода JavaScript используйте одну из двух функций ниже. Первый воплощает императивный стиль и гораздо быстрее. Последний является рекурсивным и аккуратным, но применим только к относительно небольшому количеству команд (<16384). </p>

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

Здесь вы заполняете пятна один за другим, отражая уже занятые. Например, команда, которая первой посеяла (то есть номер 0), выходит на самое верхнее место. Второй (1) занимает противоположное место в другой половине скобки. Третья команда (2) отражает 1 в своей половине кронштейна и так далее. Несмотря на вложенные циклы, алгоритм имеет линейную сложность по времени в зависимости от количества команд.

Вот рекурсивный метод:

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

По сути, вы делаете то же зеркалирование, что и в предыдущей функции, но рекурсивно:

• Для команды n = 1 это просто [0].

• Для n = 2 команд вы применяете эту функцию к аргументу n-1 (то есть 1) и получите [0]. Затем вы удваиваете массив, вставляя зеркальный элементы между ними в четных позициях. Таким образом, [0] становится [0, 1].

• Для n = 4 команд вы выполняете ту же операцию, поэтому [0, 1] становится [0, 3, 1, 2].

Если вы хотите получить удобочитаемый вывод, увеличьте каждый элемент результирующего массива на единицу:

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

Answer 9

Так как это происходит при поиске по теме, и безнадежно найти другой ответ, который решает проблему и помещает семена в «более симпатичный» порядок, я добавлю свою версию PHP-кода от darkangel.Я также добавил возможность давать прощания старшим игрокам.

Это было закодировано в ОО-среде, поэтому количество участников в $ this-> финалистах, а количество байтов в $ this-> прощания.Я тестировал только код без байсов и с двумя байтами.

  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 10

• В каждом раунде сортировка команд по критериям отбора
• (если в раунде n команд) команда на i-й позиции играет с командой n-i + 1