algorithm - Algoritmo de colocación de soporte de torneo

language-agnostic brackets

Question

Dada una lista de semillas oponentes (por ejemplo, semillas 1 a 16), estoy tratando de escribir un algoritmo que resulte en que la semilla principal juegue la semilla más baja en esa ronda, la segunda semilla que juegue la segunda semilla más baja, etc.

Agrupar 1 y 16, 2 y 15, etc. en "partidos" es bastante fácil, pero también necesito asegurarme de que la semilla más alta juegue la semilla más baja en las siguientes rondas.

Un soporte de ejemplo con la colocación correcta:

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

Como puedes ver, las semillas 1 y 2 solo se encuentran en la final.

Answer 1

Como esto surge cuando se busca el tema, y ​​es imposible encontrar otra respuesta que resuelva el problema Y ponga las semillas en un orden "más bonito", agregaré mi versión del código PHP de darkangel. También agregué la posibilidad de dar byes a los jugadores de semillas más altos.

Esto se codificó en un entorno OO, por lo que el número de participantes está en $ this-> finalists y el número de byes está en $ this-> byes. Sólo he probado el código sin byes y con dos 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;
    }

Answer 2

Con tus suposiciones, los jugadores 1 y 2 jugarán en la final, los jugadores 1-4 en las semifinales, los jugadores 1-8 en los cuartos de final, etc., para que puedas construir el torneo de forma recursiva hacia atrás desde la final como propuso AakashM. Piense en el torneo como un árbol cuya raíz es la final.

En el nodo raíz, tus jugadores son {1, 2}.

Para expandir el árbol de forma recursiva al siguiente nivel, tome todos los nodos en la capa inferior del árbol, uno por uno, y cree dos hijos para cada uno, y coloque uno de los jugadores del nodo original en cada uno de los niños. nodos creados. Luego agrega la siguiente capa de jugadores y asignalos al juego para que el peor jugador recién agregado juegue contra el mejor jugador preexistente y así sucesivamente.

Aquí las primeras rondas del algoritmo:

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

Como puedes ver, produce el mismo árbol que publicaste.

Answer 3

Para el código JavaScript, utilice una de las dos funciones siguientes. El primero encarna el estilo imperativo y es mucho más rápido. El último es recursivo y más ordenado, pero solo aplicable a un número relativamente pequeño de equipos (<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
}

Aquí se rellenan los puntos uno por uno reflejando los ya ocupados. Por ejemplo, el primer equipo sembrado (que es el número 0 ) va al lugar más alto. El segundo ( 1 ) ocupa el lugar opuesto en la otra mitad del soporte. El tercer equipo ( 2 ) refleja 1 en su mitad del soporte y así sucesivamente. A pesar de los bucles anidados, el algoritmo tiene una complejidad de tiempo lineal en función del número de equipos.

Aquí está el método recursivo:

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

Básicamente, haces el mismo reflejo que en la función anterior, pero recursivamente:

• Para n = 1 equipo, es solo [0] .

• Para n = 2 equipos, aplique esta función al argumento n-1 (es decir, 1 ) y obtenga [0] . Luego doblas la matriz insertando elementos reflejados entre ellos en posiciones iguales. Así, [0] convierte en [0, 1] .

• Para n = 4 equipos, haces la misma operación, por lo que [0, 1] convierte en [0, 3, 1, 2] .

Si desea obtener un resultado legible para las personas, aumente cada elemento de la matriz resultante en uno:

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

Answer 4

Se me ha ocurrido el siguiente algoritmo. Puede que no sea súper eficiente, pero no creo que realmente deba serlo. Está escrito en 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

También escribí una solución escrita en PHP. Vi la respuesta de Patrik Bodin, pero pensé que debía haber una manera más fácil.

Hace lo que Darkangel pidió: devuelve todas las semillas en las posiciones correctas . Los partidos son los mismos que en su ejemplo, pero en un orden más bonito , la semilla 1 y la semilla número 16 están fuera del esquema (como se ve en los torneos de tenis).

Si no hay sorpresas (lo que significa que un jugador mejor sembrado siempre gana de un jugador sembrado más bajo), terminarás con sembrado 1 vs sembrado 2 en la final.

En realidad hace dos cosas más:

1. Muestra el orden correcto (que es un requisito para poner byes en las posiciones correctas)

2. Rellena los byes en las posiciones correctas (si es necesario)

Una explicación perfecta sobre cómo debería ser un soporte de eliminación simple: http://blog.playdriven.com/2011/articles/the-not-so-simple-single-elimination-advantage-seeding/

Código de ejemplo para 16 participantes:

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

?>

La salida:

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

Si cambias 16 en 6 obtienes:

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 6

Trabajé en un complemento PHP / Laravel que genera corchetes con / sin round robin preliminar. Tal vez pueda ser útil para usted, no sé qué tecnología está utilizando. Aquí está el github.

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

¡Espero eso ayude!

Answer 7

Versión AC

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 8

Este JavaScript devuelve una matriz donde cada índice par reproduce el siguiente índice impar.

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 9

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

• En cada ronda clasifica los equipos por criterios de siembra.
• (Si hay n equipos en una ronda) el equipo en la posición i juega con el equipo n-i + 1