Jan Sauerwein
2004-05-21 14:25:14 UTC
Hallo dcm,
Ich hoffe ich bin hier richtig. Ich suche einen Algorithmus zur Auslosung
einer Round Robin.
RoundRobin: Runden-System bei Turnieren. Jeder Spieler spielt gegen jeden
anderen seiner Gruppe.
Es ist noch relativ einfach bei Partien von zwei Spielern (1:1) all
möglichen Paarungen zu finden (einfache Kombinatorik):
Bei sagen wir 6 Spielern (nummeriert von 0 bis 5):
0:1 1:2 2:3 3:4 4:5
0:2 1:3 2:4 3:5
0:3 1:4 2:5
0:4 1:5
0:5
Also 6 über 2 mögliche Partien (= 15).
Wie bekomme ich jetzt nun jedoch schon einmal alle Partien, die
gleichzeitig gespielt werden können? Möglichst ohne Backtracking?
Doch die eigentlich schwierige Fragestellung beginnt erst jetzt.
Eine RoundRobin besagt, dass jeder gegen jeden gespielt haben muss. Bei
Partien in der nur zwei Parteien antreten ist das gleich mit der Menge
aller Tupel ohne Reihenfolge.
Wenn nun aber mehr Parteien als 3 an einer Partie beteiligt sind, wird das
ganze ziemlich kompliziert.
Ein "einfaches" und kleines Beispiel:
15 Mitspieler, 3er Partie.
Das wären 455 mögliche Partien ohne Betrachtung der Reihenfolge. Dann wären
alle möglichen Spielkombinationen abgedeckt. Das ist ziemlich viel und auch
nicht nötig, da nur jeder genau einmal gegen jeden gespielt haben soll.
Übrigens wären dies 91 Runden. Und viele Stunden Spielzeit.
So nun gilt es nur die relevanten Spiele zu ermitteln. Als erstes stellt
man fest, dass nicht alle Kombinationen aus Spielerzahl und Partiegröße
funktionieren können. Doch dazu später mehr. Hier erst einmal meine
bisherige Vorgehensweise:
Ich erstelle mir eine Liste aller möglichen zweier Tupel aus den 15
Spielern (ohne Reihenfolge). In dieser Liste hake ich nun ab, ob diese
beiden Spieler bereits gegen einander gespielt haben.
Nun gehe ich die Liste aller möglichen Partien durch. Für jede Kombination
gucke ich nun ob dort bereits eine Kombination aus meiner Liste vorkommt.
Ob also schon zwei Spieler gegen einander gespielt haben. Ist das der Fall,
wird die Kombination gelöscht.
Andernfalls werden die neu hinzugekommenen in der Liste markiert. Das laufe
ich durch bis alle möglichen Kombinationen durchlaufen sind.
Bei 15 Spielern und 3er Partien klappt das. So auch bei 3 (logisch oder?),
7, 31, ..., 2^n-1 Spielern und einer 3er Partie. (getestet - nicht
bewiesen, aber da fehlte mir die Lust, solte aber mittels Vollst. Induktion
ein Leichtes sein.)
Bei allen anderen Spielerzahlen haben nach Ablauf aller Spielkombinationen
nicht alle Spieler mindestens einmal gegen jeden anderen gespielt.
Das Problem ist aber noch nicht behoben; jetzt gilt es alle Partien zu
finden, die man gleichzeitig austragen könnte. Aus obiger 35 Partien
starken Liste ist dies noch nicht so schwierig, aber bei größeren
Teilnehmerfeldern wird das schon schwieriger. Ein generischer Algorithmus?
Meine Frage bezieht sich auf die Verallgemeinerung für beliebige
Partiegrößen und Teilnehmerfelder (bis mindestens 8), die Auslosung
parallel spielbarer Partien und einen Algorithmus, der mir vor Beginn der
ersten Auslosung sagt, ob die Kombination aus Teilnehmerzahl und
Partiegröße funktioniert.
Sollte das noch viel zu einfach gewesen sein. Wäre es fast perfekt das
ganze auch noch für variable Partiegrößen ermitteln zu können. Zum Beispiel
möchte man 6er und 8er Partien zulassen. Welche Anforderungen ergeben sich
daraus, und wie muss ausgelost werden.
Der Algorithmus kann ruhig etwas länger dauern, da ich mich bereits davon
verabschiedet habe, dies jedes mal für jedes Turnier neu auszurechnen und
statt dessen meinem Programm Schablonen mitzugeben.
Jeder Tipp und Denkansatz zu einer Lösung ist mir willkommen.
Vielen Dank schon einmal im Voraus.
Jan Sauerwein
Ich hoffe ich bin hier richtig. Ich suche einen Algorithmus zur Auslosung
einer Round Robin.
RoundRobin: Runden-System bei Turnieren. Jeder Spieler spielt gegen jeden
anderen seiner Gruppe.
Es ist noch relativ einfach bei Partien von zwei Spielern (1:1) all
möglichen Paarungen zu finden (einfache Kombinatorik):
Bei sagen wir 6 Spielern (nummeriert von 0 bis 5):
0:1 1:2 2:3 3:4 4:5
0:2 1:3 2:4 3:5
0:3 1:4 2:5
0:4 1:5
0:5
Also 6 über 2 mögliche Partien (= 15).
Wie bekomme ich jetzt nun jedoch schon einmal alle Partien, die
gleichzeitig gespielt werden können? Möglichst ohne Backtracking?
Doch die eigentlich schwierige Fragestellung beginnt erst jetzt.
Eine RoundRobin besagt, dass jeder gegen jeden gespielt haben muss. Bei
Partien in der nur zwei Parteien antreten ist das gleich mit der Menge
aller Tupel ohne Reihenfolge.
Wenn nun aber mehr Parteien als 3 an einer Partie beteiligt sind, wird das
ganze ziemlich kompliziert.
Ein "einfaches" und kleines Beispiel:
15 Mitspieler, 3er Partie.
Das wären 455 mögliche Partien ohne Betrachtung der Reihenfolge. Dann wären
alle möglichen Spielkombinationen abgedeckt. Das ist ziemlich viel und auch
nicht nötig, da nur jeder genau einmal gegen jeden gespielt haben soll.
Übrigens wären dies 91 Runden. Und viele Stunden Spielzeit.
So nun gilt es nur die relevanten Spiele zu ermitteln. Als erstes stellt
man fest, dass nicht alle Kombinationen aus Spielerzahl und Partiegröße
funktionieren können. Doch dazu später mehr. Hier erst einmal meine
bisherige Vorgehensweise:
Ich erstelle mir eine Liste aller möglichen zweier Tupel aus den 15
Spielern (ohne Reihenfolge). In dieser Liste hake ich nun ab, ob diese
beiden Spieler bereits gegen einander gespielt haben.
Nun gehe ich die Liste aller möglichen Partien durch. Für jede Kombination
gucke ich nun ob dort bereits eine Kombination aus meiner Liste vorkommt.
Ob also schon zwei Spieler gegen einander gespielt haben. Ist das der Fall,
wird die Kombination gelöscht.
Andernfalls werden die neu hinzugekommenen in der Liste markiert. Das laufe
ich durch bis alle möglichen Kombinationen durchlaufen sind.
Bei 15 Spielern und 3er Partien klappt das. So auch bei 3 (logisch oder?),
7, 31, ..., 2^n-1 Spielern und einer 3er Partie. (getestet - nicht
bewiesen, aber da fehlte mir die Lust, solte aber mittels Vollst. Induktion
ein Leichtes sein.)
Bei allen anderen Spielerzahlen haben nach Ablauf aller Spielkombinationen
nicht alle Spieler mindestens einmal gegen jeden anderen gespielt.
Das Problem ist aber noch nicht behoben; jetzt gilt es alle Partien zu
finden, die man gleichzeitig austragen könnte. Aus obiger 35 Partien
starken Liste ist dies noch nicht so schwierig, aber bei größeren
Teilnehmerfeldern wird das schon schwieriger. Ein generischer Algorithmus?
Meine Frage bezieht sich auf die Verallgemeinerung für beliebige
Partiegrößen und Teilnehmerfelder (bis mindestens 8), die Auslosung
parallel spielbarer Partien und einen Algorithmus, der mir vor Beginn der
ersten Auslosung sagt, ob die Kombination aus Teilnehmerzahl und
Partiegröße funktioniert.
Sollte das noch viel zu einfach gewesen sein. Wäre es fast perfekt das
ganze auch noch für variable Partiegrößen ermitteln zu können. Zum Beispiel
möchte man 6er und 8er Partien zulassen. Welche Anforderungen ergeben sich
daraus, und wie muss ausgelost werden.
Der Algorithmus kann ruhig etwas länger dauern, da ich mich bereits davon
verabschiedet habe, dies jedes mal für jedes Turnier neu auszurechnen und
statt dessen meinem Programm Schablonen mitzugeben.
Jeder Tipp und Denkansatz zu einer Lösung ist mir willkommen.
Vielen Dank schon einmal im Voraus.
Jan Sauerwein