Algorithme de placement des crochets de tournois

Ce JavaScript renvoie un tableau où chaque index Pair joue l'index Impair suivant

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]

avec vos suppositions, les joueurs 1 et 2 joueront en finale, les joueurs 1-4 en demi-finale, les joueurs 1-8 en quart de finale et ainsi de suite, de sorte que vous pouvez construire le tournoi récursivement à l'envers à partir de la finale comme AakashM proposé. Penser le tournoi comme un arbre dont la racine est la finale.

dans le noeud racine, vos joueurs sont {1, 2}.

pour étendre l'arbre de façon récursive au niveau suivant, prendre tous les noeuds sur la couche inférieure de l'arbre, un par un, et créer deux enfants pour chacun d'eux, et placer un des joueurs du noeud original à chacun des noeuds enfant créés. Puis Ajouter la couche suivante de joueurs et les mapper au jeu de sorte que le pire joueur nouvellement ajouté joue contre le meilleur joueur préexistant et ainsi de suite.

Voici les premiers rounds de l'algorithme:

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

Comme vous pouvez le voir, il produit le même arbre que vous avez posté.

j'ai aussi écrit une solution écrite en PHP. J'ai vu la réponse DE Patrik Bodin, mais j'ai pensé qu'il devait y avoir un moyen plus facile.

il fait ce que darkangel a demandé: il renvoie toutes les graines dans les bonnes positions. Les matchs sont les mêmes que dans son exemple, mais dans un plus jolie ordre, seed 1 et seed number 16 sont à l'extérieur du schéma (comme vous le voyez dans les tournois de tennis).

S'il n'y a pas de problèmes (ce qui signifie qu'un joueur ayant un nombre de joueurs supérieur gagne toujours) à partir d'un joueur semé plus bas), vous finirez avec seed 1 vs seed 2 en finale.

C'est en fait deux choses les plus:

1. il montre l'ordre correct (qui est une condition pour mettre byes dans les positions correctes)

2. il remplit byes dans les bonnes positions (si nécessaire)

une explication parfaite de ce à quoi un seul support d'élimination devrait ressembler: http://blog.playdriven.com/2011/articles/the-not-so-simple-single-elimination-advantage-seeding/

exemple de Code pour 16 participants:

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

?>

Le résultat:

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 vous changez 16 en 6 vous obtenez:

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

# 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

• à chaque ronde trier les équipes par critères de semis
• (S'il y a n équipes dans une ronde)équipe à la ième position joue avec l'équipe n-i+1

puisque cela se produit lors de la recherche sur le sujet, et il est sans espoir de trouver une autre réponse qui résout le problème et met les graines dans un "plus joli" ordre, je vais ajouter ma version du code PHP de darkangel. J'ai également ajouté la possibilité de donner des byes aux joueurs de seed supérieurs.

ceci a été codé dans un environnement OO, donc le nombre de participants est en $this->finalistes et le nombre de byes est en $this->byes. J'ai seulement testé le code, sans exemptions et avec deux revoir.

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

Pour le code JavaScript, utilisez l'une des deux fonctions ci-dessous. Le premier incarne le style impératif et est beaucoup plus rapide. Ce dernier est récursif et plus net, mais ne s'applique qu'à un nombre relativement restreint d'équipes (<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
}

ici vous remplissez les spots un par un en reproduisant ceux déjà occupés. Par exemple, la première équipe (c'est-à-dire le nombre 0) va à l'endroit le plus haut. La seconde (1) occupe la position opposée dans l'autre moitié du support. La troisième équipe (2) miroirs 1 dans leur moitié de support et ainsi de suite. Malgré les boucles imbriquées, l'algorithme a une complexité de temps linéaire en fonction du nombre d'équipes.

Voici la méthode récursive:

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

fondamentalement, vous faites le même mirroring que dans la fonction précédente, mais récursivement:

• n = 1 l'équipe, c'est juste [0].

• n = 2 équipes, vous appliquez ceci la fonction de l'argument n-1 (c'est, 1) & get [0]. Puis vous doublez le tableau en insérant un miroir les éléments entre eux à même les postes. Ainsi,[0] devient [0, 1].

• n = 4 équipes, vous faites la même opération, de sorte que [0, 1] devient [0, 3, 1, 2].

si vous voulez obtenir une sortie lisible par l'humain, augmentez chaque élément du tableau résultant d'un:

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

j'ai travaillé sur un plugin PHP / Laravel qui génère des crochets avec / sans Round robin préliminaire. Peut-être que ça peut vous être utile, Je ne sais pas quelle technologie vous utilisez. Voici le github.

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

j'Espère que ça aide!

A C version.

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