Javascript ist Toll!

Robin round Berechnung mit Javascript

Das Robin Round System, ist ein Algorithmus zur Berechnung von Spielpaarungen in einem rundenbasierten Turnier. Das sind z.b. alle Turniere vieler Ballsportarten. Das Problem bei der Berechnung sind die folgenden Rahmenbedingunen.

• 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 wird ein "Geisterteam" eingefügt. Der jeweilige Gegner dieses Team hat eine Spielpause. Alle Teams, bis auf eines, werden in einem Vieleck angeordnet. Das eine Team wird fixiert und die anderen Teams rotieren. 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.

Ich habe diesen Algorithmus nicht 100% umgesetzt, weil Javascript einen Bug, bzw. eine andere Art der Berechnung, bei der Modulo-Funktion hat. Das ist aber nicht weiter problematisch, da das in dem Artikel erwähnte Problem mit Javascript eigentlich keines ist. Die Rotation der Zahlen läßt sich sehr 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() + ' Teams\n';

};

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.