Tri des graines de tournoi

Les idées des joueurs correspondants du haut et du bas sont correctes mais pas tout à fait complète. Le faire une fois fonctionne bien pour le premier tour: xxx pré>

... Mais au second tour, la graine 1 rencontre la graine 2 et 3 rencontre 4. Nous devons faire le premier / dernier shuffle pour chaque tour. Première fois, nous déplaçons chaque élément individuellement fort>. Deuxième fois, nous déplacons chaque paire forte> d'éléments. Troisièmement, la troisième fois que nous déplacons groupes de quatre forts>, etc., jusqu'à ce que notre taille de groupe soit graines.Length / 2 code>. Comme: p> xxx pré>

Voici ce que la matrice ressemblera à la travers des itérations (la parenthèse indique la taille croissante du groupe): P>

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)

Voici l'algorithme que j'ai développé. L'étape 1 est de dessiner une table avec autant de lignes qu'il existe des équipes (arrondies à une puissance de 2) et autant de colonnes que nécessaire pour représenter le nombre d'équipes en binaire. Dis, il y a 8 équipes. La table ressemblera d'abord à ceci (les points représentent des bordures de cellules horizontales):

. . . | | | | . . . | | | | . . . | | | | . . . | | | | . . . | | | | . . . | | | | . . . | | | | . . . | | | | . . .

Les colonnes sont numérotées à partir de la gauche dans l'ordre croissant. Pour chaque colonne, mettez un astérisque tous les 2 ^ (numéro de colonne). C'est-à-dire toutes les 2èmes rangées de la colonne 1, toutes les 4èmes rangées de la colonne 2 etc.

. . . | | | | . . . | | | | *. . | | | | . . . | | | | * *. | | | | . . . | | | | *. . | | | | . . . | | | |

Commencez avec un 0 dans chaque colonne de la 1ère rangée. Par la suite, pour des lignes successives dans chaque colonne bascule de 0-1 et 1-0 à moins d'un astérisque dans cette rangée. C'est le résultat:

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

La dernière étape consiste à évaluer chaque ligne de traitement de la chaîne de 0 et 1 sous forme de numéro binaire. Cela entraînera des valeurs de 0 à 7. Ajout de 1 à chaque résultat des valeurs de 1 à 8. Celles-ci correspondent aux semis.

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

Chaque paire de graines sont les allumettes à jouer dans l'ordre. c'est à dire. 1-8, 5-4, 3-6 et 7-2. Ceci est extensible à n'importe quel nombre de graines. Lorsque les byes doivent être insérés en raison du nombre d'entrées étant inférieures à une puissance de 2, elles prennent les valeurs de semences les plus élevées. par exemple. S'il n'y avait que 28 entrées, les byes prennent les positions attribuées à 29, 30, 31 et 32.

J'ai écrit une solution en PHP (voir https://stackoverflow.com/a/45566890/760777 ). Voici la version JavaScript.

Il renvoie toutes les graines dans les bonnes positions forte>. Les matchs sont les mêmes que dans son exemple, mais dans un ordre plus jolie EM>, la graine 1 et la graine numéro 8 sont à l'extérieur du schéma (comme vous le voyez dans des tournois de tennis). P> S'il n'y a pas de bouleversement (ce qui signifie qu'un joueur ensemencé supérieur gagne toujours à partir d'un joueur grillé inférieur), vous vous retrouverez avec une graine 1 vs graine 2 en finale. p>

Cela fait en réalité deux choses plus: p>

1. Il montre le bon ordre (qui est une condition nécessaire pour mettre les byes dans les bonnes positions) p> li>

2. Il remplit les byes dans les bonnes positions (si nécessaire) p> li> ol>

   Une explication parfaite sur ce qu'on doit ressembler à un seul support d'élimination: http://blog.playdriven.com/2011/articles/Le-not-so-simple-single-élimination-Avantage-evantage-Avantage-Éxéivant/ P >

   Exemple de code pour 8 participants: p>

   p>

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

J'étais vraiment intrigué et impressionné par l'algorithme de Cliff ici . Je pense que c'est très intelligent. Voici une simple mise en œuvre que j'ai écrite dans Ruby. Les byes sont retournés comme -1.

seed(8)
=> [1, 8, 5, 4, 3, 6, 7, 2]

seed(6)
=> [1, -1, 5, 4, 3, 6, -1, 2]