Алгоритм размещения кронштейнов турнира
Учитывая список семян противника (например, семена с 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 встречаются только в финале.
Ответы
Ответ 1
Я придумал следующий алгоритм. Это может быть не очень эффективно, но я не думаю, что это действительно нужно. Написано на 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);
}
?>
Ответ 2
Этот 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]
Ответ 3
С вашими предположениями игроки 1 и 2 будут играть в финале, игроки 1-4 в полуфинале, игроки 1-8 в четвертьфинале и т.д., поэтому вы можете реорганизовать турнир назад из финала, как предложил AakashM, Подумайте о турнире как о дереве, корень которого является окончательным.
В корневом каталоге node ваши игроки будут {1, 2}.
Чтобы реверсировать дерево на следующий уровень, возьмите все узлы нижнего слоя в дереве один за другим и создайте для них двое детей и поместите один из игроков исходного node в каждый из созданных дочерних узлов. Затем добавьте следующий слой игроков и сопоставьте их с игрой, чтобы худший вновь добавленный игрок играл против лучшего уже существующего игрока и т.д.
Здесь первые раунды алгоритма:
{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}
Как вы можете видеть, он создает одно и то же дерево, которое вы разместили.
Ответ 4
Я также написал решение, написанное на PHP. Я видел Патрика Бодина, но думал, что должен быть более простой способ.
Он делает то, о чем просил darkangel: он возвращает все семена в правильных положениях. Матчи такие же, как в его примере, но в более хорошем порядке семена 1 и семенной номер 16 находятся снаружи схемы (как вы видите в турнирах по теннису).
Если нет расстроек (это означает, что игрок с более высоким посевом всегда выигрывает от игрока с более низким посевом), вы получите семя 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
Ответ 5
# Here 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
Ответ 6
- В каждом раунде сортировать команды по критериям посева.
- (Если есть n команд в раунде) команда в i-й позиции играет с командой n-i + 1
Ответ 7
Так как это возникает при поиске по этому вопросу, и он безнадежно найти другой ответ, который решает проблему И помещает семена в "более красивый" порядок, я добавлю свою версию кода PHP из darkangel. Я также добавил возможность давать байки более старшим игрокам.
Это было закодировано в среде OO, поэтому количество участников находится в $this- > finalists, а количество байтов в $this- > byes. Я только проверил код без байтов и с двумя байтами.
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;
}
Ответ 8
Для кода JavaScript используйте одну из двух функций ниже. Первый воплощает императивный стиль и намного быстрее. Последний является рекурсивным и более аккуратным, но применим только к относительно небольшому числу команд (< 16384).
// 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)
Ответ 9
Я работал над плагином PHP/Laravel, который генерирует скобки с/без предварительного раунда. Может быть, это может быть полезно для вас, я не знаю, какую технологию вы используете. Вот гитуб.
https://github.com/xoco70/kendo-tournaments
Надеюсь, что это поможет!
Ответ 10
Версия 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;
}
