Ich beginne damit zu sagen, dass ich verstehe, dass dieses Thema kompliziert ist und dass es wahrscheinlich keine einfache Antwort gibt. Wenn es einfach wäre, würde jeder es tun. Das sagte ...
Ich wurde gebeten, eine Anwendung zu erstellen, um eine Sportliga zu verwalten. Die meisten Konzepte sind ziemlich einfach zu verstehen, außer für dieses: Wie man einen Spielplan erstellt, wo es keine Überlappungen gibt (Team spielt 2 Teams gleichzeitig), wo ein Team in einer Division seine Teams zweimal spielt, aber Teams von der andere Abteilungen einmal, und stellt sicher, dass es keine Löcher im Zeitplan gibt (jedes Team spielt jede Woche)
Momentan wird der Prozess manuell mit einer Tabellenkalkulation vom Typ "rosetta stone" durchgeführt, die ich für diesen Zweck entwickelt habe, aber er funktioniert nur für die Anzahl der Teams, für die er entworfen wurde. Ich habe Variationen für 30 Teams, 24 Teams und 28 Teams gemacht. Anstatt ständig versuchen, meine Übersetzungstabelle neu zu justieren, würde ich gerne in der Lage sein, diese Logik zu kodifizieren und stattdessen diesen Prozess zu optimieren.
Gedanken?
Es gibt ein ziemlich einfaches System, das z.B. Schachturniere namens Round-Robin.
Die Idee besteht darin, die Spieler auf zwei Seiten eines Tisches aufzuteilen. Einer der Spieler wird als "Hub" (für ein besseres Wort) bezeichnet. Das Turnier beginnt damit, dass sich die Spieler gegenüberstehen und gegeneinander spielen. Nach der ersten Runde zieht jeder außer dem Hub einen Stuhl nach vorne und der Weiß / Schwarz-Auftrag (Heim / Auswärts im Sport) wird geschaltet. Der gesamte Round-Robin-Wettbewerb ist beendet, wenn die Spieler an ihren ursprünglichen Plätzen sitzen. Wenn Sie möchten, dass jeder alle zweimal spielt, machen Sie dasselbe erneut.
Wikipedia-Artikel mit Details zur Implementierung.
In Ihrem speziellen Fall würde ich versuchen, das Round Robin einmal mit allen Teams zu machen. Dann machen Sie das gleiche für jede Division einmal und um sicherzustellen, dass sich Teams innerhalb der Divisionen einmal zu Hause und einmal in der Ferne spielen, prüfen Sie ab der ersten Runde, wie die Mannschaften in dieser Runde gespielt haben.
Der Nachteil davon ist natürlich, dass Sie alle Spiele zwischen den Divisionen lange vor dem Ende des Turniers spielen werden (da die letzten n-1 Spiele gegen Teams innerhalb der Division sind [n = Anzahl der Teams in der Division ]). Wenn das ein Problem ist, könntest du die Spiele einfach ein bisschen herum tauschen.
Ich habe tatsächlich ein einfaches Python-Skript geschrieben, das das tut. Es brauchte nicht viele Codezeilen und erzeugte ziemlich gute Ergebnisse. Dadurch wird ein Zeitplan erstellt, in dem jede Mannschaft zwei Teams in ihrer Division zweimal und einmal gegen Teams in anderen Divisionen spielt. Es wird nicht überprüft, ob die Mannschaften sich zweimal so treffen, dass die gleiche Mannschaft zu Hause ist. Aber dieser Code sollte eine gute Idee geben, wie man seinen eigenen Terminierungscode erstellt.
%Vor%Es gibt zwei Algorithmen, einen für ungerade Teams, einen für gerade Teams, um sicherzustellen, dass das Round-Robin passiert.
Ich werde dir eine Grafik erstellen, wenn ich kann.
ODD Anzahl der Teams
Der Algorithmus soll alle Teams im Uhrzeigersinn drehen. Wenn wir 5 Teams hätten:
%Vor%An diesem Punkt haben wir ein Round Robin absolviert, wo jeder einmal spielt ... die nächste Runde wäre wieder ..
%Vor%EVEN # Teams
Wenn wir eine gerade Anzahl von Teams haben, machen Sie die gleiche Rotation, außer dass Sie Team # 1 in einer festen Position halten und alle anderen Teams um # 1 herum im Uhrzeigersinn drehen. Also, wenn wir 4 Teams hätten ..
%Vor%Das wäre ein komplettes Round Robin ... das nächste Match wäre ... ..
%Vor%programmatisch, es gibt ein paar Möglichkeiten, wie Sie das angehen könnten. Vielleicht tut der Code, der oben gepostet wird, das gleiche lol ..
Ich würde diese Einschränkungen einfach als boolesche Formel kodieren und einige SAT-Solver verwenden, um Lösungen zu erhalten (z. B. MiniSAT für C ++, SAT4J für Java und Sie könnten sogar Ihren eigenen einfachen Solver schreiben). Die Eingabe für diese Solver wird von DIMACS standardisiert.
Siehe auch "Eine SAT-Kodierung für das soziale Golfer-Problem" und "Ein SAT-basierter Scheduler für Turnierpläne" für SAT-Kodierungen ähnlicher Probleme.
Hier ist eine Einstellung zu einer Implementierung
%Vor%Ich habe es nur auf Papier getestet, aber für mein Setup funktioniert es. Indem ich zwischen dem Beginn der Liste der Mannschaften und dem Ende der Liste wechsle, vermeide ich die Situationen, in denen die gleiche Mannschaft immer wieder dieselbe Mannschaft spielen muss (oder wiederholt am selben Tag spielen muss) repräsentierte jede mögliche Begegnung als einen anderen Opponenten, aber das ist im Grunde, was die CanPlay-Methode tun sollte. Hoffe, das hilft, obwohl es keine vollständige Lösung