Javascript ist Toll!

Round Robin Berechnung mit Javascript

Mit dem Round Robin Algorithmus können Spielpaarungen in einem rundenbasierten Turnier berechnet werden. Das betrifft z.b. Turniere vieler Ballsportarten. Das Besondere an diesem Algorithmus ist, dass sich die Spiele mit den folgenden Rahmenbedingungen berechnen lassen:

• Jedes Team soll möglichst abwechselnd Heim- und Auswärtsrecht haben
• Jedes Team soll jede Spielrunde ein Spiel austragen

Der Algorithmus wird wie folgt angewandt:

Zunächst muss die Anzahl der Teams eine gerade Zahl sein, bei einer ungeraden Anzahl von Teams wird ein "Geisterteam" eingefügt. Der jeweilige Gegner dieses Team hat dann Spielpause. Alle Teams, bis auf eines, werden in einem Vieleck angeordnet. Ein Team wird fixiert und die anderen Teams rotieren in diesem Vieleck. Dann werden die Spielpaarungen anhand von Diagonalen in dem Vieleck beschrieben. Das läßt sich visualisiert besser verstehen, auf der Seite Algorithmus der Woche wird eine Variante von Sigrid Knust beschrieben und anhand von Grafiken die Funktionsweise gezeigt.

Meine Umsetzung entspricht nicht 100% der dortigen, weil Javascript einen Bug, bzw. eine andere Art der Berechnung, bei der Modulo-Funktion hat. Das ist aber nicht weiter problematisch. Die Rotation der Zahlen läßt sich einfach mit einem Array und den dazugehörigen Funktionen umsetzen. Im Prinzip ist es nur diese Zeile t.push(t.shift()); die das Array in der gewünschten Form "rotieren" läßt.

Hier nun eine Umsetzung dieses Algorithmus mit JS.

Download

round-robin.js

Beim erzeugen des Objekt RoundRobin() muss eine Anzahl von Teams übergeben werden. Die folgenden Methoden können aufgerufen werden:

teams()

Anzahl der Teams

rounds()

Anzahl der Spielrunden

calc()

Berechnung der Spielepaarungen. Der Rückgabewert ist ein zeidimensonales Array, in der Form

[ [#num1, #num2], [#num3, #num4], ... ],
[ [#num1, #num2], [#num3, #num4], ...  ]
...

Rückgabe: [Array]

out()

Um das Array auszugeben, kann diese Methode aufgerufen werden. Dazu müssen Eventfunktionen erzeugt werden. Folgende Events werden getriggert, wenn die Funktion out() aufgerufen wird:

• onstart - Bevor die Ausgabe startet
• onround_start - Vor jeder Spielrunde
• onround - Bei jeder Spielepaarung
• onround_end - Nach jeder Spielrunde
• onend - Ende der Ausgabe

Beispiel

var league = new RoundRobin(6);
var txt = '';
league.onstart = function() {
    txt = 'Spielpaarungen für ' + this.teams() + ' Teamsn';
};
league.onround_start = function(e) {
    txt += 'Runde ' + e.round + ': ';
};
league.onround = function(e) {
    txt += '[ ' + e.pair + ']';
};
league.onround_end = function(e) {
    txt += 'n';
};
league.onend = function(e) {
    alert(txt);
};
 
league.calc();
league.out();

Links zum Thema

• wikipedia
• Porter-Crenshaw-Berger Tables - Variationen verschiedener Algorithmen, die andere Rahmenbedingungen z.b. für ein Schachturnier, berücksichtigen.