Sortieren Turnier-Samen

Question

Ich erstelle eine HTML/JS-basierte Single/Double-Elimination-Bracket-Web-App. Ich habe Schwierigkeiten herauszufinden, wie ich die Erstrunden-Matches aus einer Liste von gesetzten Teams/Spielern zuweisen kann. Zum Beispiel, in einem K.-o.-System von 8 Spielern, sind die Erstrunden-Matches:

1v8 4v5 2v7 3v6

In allgemeineren Begriffen können die gesetzten Teams als ein Array betrachtet werden (da ich Teams den Matches zuweise, indem ich sie aus einem Array herausnehme): 1,2,3,4,5,6,7,8

was sortiert werden muss zu: 1,8,4,5,2,7,3,6

Zur Klarstellung, die höheren gesetzten Teams müssen den maximalen Abstand zwischen sich im sortierten Array haben, dies geschieht, damit in einem Bracket ohne Überraschungen die niedrigeren gesetzten Teams zuerst ausscheiden und Matches mit den höheren gesetzten Teams so spät wie möglich stattfinden. In praktischen Begriffen, denken Sie an ein Tennisturnier, bei dem Sie verhindern möchten, dass die top 4 Spieler in einem K.-o.-System von 16 oder 32 etc. bis zum Halbfinale gegeneinander antreten. Also, die richtige Array-Ausgabe für ein 16 gesetztes Bracket ist:

1,16,8,9,4,13,5,12,2,15,7,10,3,14,6,11

was folgende 1. Rundenmatches übersetzt:

1v16 8v9 4v13 5v12 2v15 7v10 3v14 6v11

Danke an Matt Ball für den richtigen Algorithmus für ein 8 gesetztes Bracket

Answer 1

Die Idee, Spieler von oben und unten zu kombinieren, ist korrekt, aber nicht ganz vollständig. Beim ersten Mal funktioniert es großartig für die erste Runde:

while (seeds.length)
{
    firstRound.push(seeds.shift());
    firstRound.push(seeds.pop());
}
1, 2, 3, 4, 5, 6, 7, 8 => 1, 8, 2, 7, 3, 6, 4, 5

... aber in der zweiten Runde trifft Samen 1 auf Samen 2 und 3 auf 4. Wir müssen das Mischen von Anfang und Ende für jede Runde durchführen. Beim ersten Mal bewegen wir jedes Element einzeln. Beim zweiten Mal bewegen wir jedes Paar von Elementen. Beim dritten Mal bewegen wir Gruppen von vier, usw., bis unsere Gruppengröße seeds.length/2 beträgt. So:

// dies ist Ruby, auch bekannt als Javascript-Pseudocode :)

bracket_list = seeds.clone

slice = 1
while slice < bracket_list.length/2
  temp = bracket_list
  bracket_list = []

  while temp.length > 0
    bracket_list.concat temp.slice!(0, slice)       # n vom Anfang
    bracket_list.concat temp.slice!(-slice, slice)  # n vom Ende
  end

  slice *= 2
end
return bracket_list

So sieht das Array aus, wenn Sie durch die Iterationen gehen (Klammern zeigen die zunehmende Gruppengröße an):

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)

Also, nachdem die unteren 8 Spieler ausscheiden, bleiben uns 1, 8, 4, 5, 2, 7, 3, 6. Nachdem die unteren 4 von dort ausgeschieden sind, haben wir 1, 4, 2, 3, und im letzten Durchgang nur noch 1, 2.

Es ist schwierig, dies zu erklären, ohne eine Tabelle zeichnen zu können... Lassen Sie mich wissen, ob ich etwas für Sie klarstellen kann.

Answer 2

Ich habe eine Lösung in PHP geschrieben (siehe https://stackoverflow.com/a/45566890/760777). Hier ist die JavaScript-Version.

Es gibt alle Seeds in den richtigen Positionen zurück. Die Übereinstimmungen sind dieselben wie in seinem Beispiel, aber in einer schöneren Reihenfolge, Seed 1 und Seed Nummer 8 befinden sich außerhalb des Schemas (wie bei Tennis-Turnieren).

Wenn es keine Überraschungen gibt (was bedeutet, dass ein höher gesetzter Spieler immer gegen einen niedriger gesetzten Spieler gewinnt), kommst du im Finale zu Seed 1 vs Seed 2.

Es macht tatsächlich zwei Dinge mehr:

1. Es zeigt die richtige Reihenfolge (was eine Voraussetzung dafür ist, Byes an den richtigen Positionen zu platzieren)

2. Es füllt Byes an den richtigen Positionen ein (falls erforderlich)

Eine perfekte Erklärung darüber, wie ein Single-Elimination-Bracket aussehen sollte: http://blog.playdriven.com/2011/articles/the-not-so-simple-single-elimination-advantage-seeding/

Code-Beispiel für 8 Teilnehmer:

var NUMBER_OF_PARTICIPANTS = 8; // Setze die Anzahl der Teilnehmer

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("Anzahl der Teilnehmer: {0}".format(participantsCount));
  console.log("Anzahl der Runden: {0}".format(rounds));
  console.log("Bracket-Größe: {0}".format(bracketSize));
  console.log("Erforderliche Anzahl von 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;
}

Ändere NUMBER_OF_PARTICIPANTS von 8 auf 6, um zwei Byes zu erhalten.

Viel Glück. RWC

Answer 3

Dies ist wahrscheinlich nicht so effizient wie @alex's Antwort mit einer benutzerdefinierten sort Funktion, aber sicherlich einfacher zu schreiben und zu verstehen:

// Dieser Algorithmus geht davon aus, dass seeds.length eine gerade Zahl ist
var seeds = [1, 2, 3, 4, 5, 6, 7, 8],
    firstRound = [];

while (seeds.length)
{
    firstRound.push(seeds.shift());
    firstRound.push(seeds.pop());
}

// seeds ist jetzt leer
// firstRound ist jetzt [1, 8, 2, 7, 3, 6, 4, 5]

Demo 1

---

Eigentlich ist mir gerade ein schnellerer Algorithmus eingefallen (In-Place "Sortierung", dauert O(n) Zeit):

// Geht ebenfalls davon aus, dass seeds.length eine gerade Zahl ist
var seeds = [1, 2, 3, 4, 5, 6, 7, 8],
    numSeeds = seeds.length,
    stop = numSeeds >> 1,
    temp;

for (var i=1; i

``

Demo 2

Zu beachten ist, dass keiner dieser Algorithmen genau die gleiche Reihenfolge von Paaren wie im OP erzeugt, aber sie erzeugen beide die gleiche Menge von Paaren:

• (1,8)
• (2,7)
• (3,6)
• (4,5)

``

Answer 4

Ich habe eine Lösung gefunden, die aber über den Rahmen von einfachem "Sortieren von Arrays" hinausgeht.

Der (Javascript-) Code befindet sich unter http://jsbin.com/ukomo5/2/edit.

Im Grunde geht der Algorithmus davon aus, dass es während des Turniers keine Überraschungen gibt, daher sollten die Samen 1 und 2 im Finale aufeinandertreffen. Er durchläuft jeden Samen in jeder Runde (beginnend vom vorberechneten großen Finale und rückwärts arbeitend), um den unbekannten Samen im vorherigen Match zu berechnen, den der aktuelle Samen (in der Iteration) gewonnen hatte. Dies kann erreicht werden, da man anhand eines Samens und der Rundenzahl herausfinden kann, welcher andere Samen es sein sollte:

anderer Samen = Anzahl der Samen in der Runde + 1 - der bekannte Samen

Zur Veranschaulichung, in den Halbfinals:

Halbfinale 1 (wo der bekannte Samen 1 ist): anderer Samen = 4 + 1 - 1 = 4

Halbfinale 2 (wo der bekannte Samen 2 ist): anderer Samen = 4 + 1 - 2 = 3

Ich habe dieses Muster bemerkt, als ich einen "keine Überraschungen" Bracket angesehen habe, den ich erstellt hatte.

In der letzten Iteration (also Runde 1) sind alle Samen und ihre Position bekannt, um den Matches zugewiesen zu werden. Das korrekte sortierte Array lautet wie folgt:

1,16,8,9,4,13,5,12,2,15,7,10,3,14,6,11

Nochmals vielen Dank an Matt Ball, der eine korrekte Lösung für kleine Brackets gefunden hat (Es ist schwierig, das Problem und die gewünschte Lösung ohne detaillierten Kontext zu erklären, was ich in meiner ursprünglichen Frage nicht komplett gemacht habe).

Falls jemand eine andere Lösung oder eine elegantere Version meiner Lösung hat, lasst es uns wissen!

Answer 5

Hier ist der Algorithmus, den ich entwickelt habe. Schritt 1 besteht darin, eine Tabelle mit so vielen Zeilen wie Teams zu zeichnen (aufgerundet auf eine Zweierpotenz) und so vielen Spalten, wie zur Darstellung der Anzahl der Teams in Binärform benötigt werden. Angenommen, es gibt 8 Teams. Die Tabelle wird zunächst so aussehen (die Punkte repräsentieren horizontale Zellgrenzen):

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

Die Spalten sind von links nach rechts aufsteigend nummeriert. Setzen Sie für jede Spalte in jeder 2^(Spaltennummer) Reihe ein Sternchen. Das heißt, jede 2. Reihe in Spalte 1, jede 4. Reihe in Spalte 2 usw.

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

---

Beginnen Sie in der 1. Zeile mit einer 0 in jeder Spalte. Danach, für aufeinanderfolgende Zeilen in jeder Spalte, wechseln Sie von 0-1 und 1-0, es sei denn, es befindet sich ein Sternchen in dieser Reihe. Das ist das Ergebnis:

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

---

Der letzte Schritt besteht darin, jede Zeile zu bewerten und die Zeichenfolge von 0ern und 1en als Binärzahl zu behandeln. Dies führt zu Werten von 0-7. Wenn Sie zu jedem 1 hinzufügen, ergeben sich Werte von 1-8. Diese entsprechen den Setzungen.

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

---

Jedes Paar Setzungen sind die zu spielenden Matches in der Reihenfolge. z.B. 1-8, 5-4, 3-6 und 7-2. Dies kann auf beliebig viele Setzungen erweitert werden. Wenn Freilose aufgrund der Anzahl der Einträge eingefügt werden müssen und diese weniger als eine Zweierpotenz sind, nehmen sie die höchsten Setzwerte ein. z.B. Wenn es nur 28 Einträge gibt, dann nehmen die Freilose die Positionen ein, die den Werten 29, 30, 31 und 32 zugewiesen sind.