Wie automatisch einen Sport-Liga-Zeitplan zu generieren

Question

Ich werde damit anfangen 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)

Im Moment wird der Prozess manuell mit einer Rosetta-Stein-Typ-Tabelle, die ich gebaut habe, um diesen Zweck zu dienen, aber es funktioniert nur für die Anzahl der Teams, für die es 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?

Answer 1

Es gibt ein ziemlich einfaches System, das z. Schachturniere, genannt Round-Robin.

Die Idee ist, die Spieler auf die zwei Seiten eines Tisches zu teilen. 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 zweimal spielt, machen Sie das Gleiche erneut.

Wikipedia article mit Implementierungsdetails.

In Ihrem speziellen Fall würde ich versuchen, das Round Robin einmal einschließlich aller Teams zu tun. Dann machen Sie das gleiche für jede Division einmal und um sicherzustellen, dass sich Teams innerhalb der Divisionen einmal zu Hause spielen und einmal weg, überprü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 Aufteilung]). Wenn das ein Problem ist, könntest du die Matches einfach ein bisschen herum tauschen.

Ich schrieb tatsächlich ein einfaches Python-Skript, das dies 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 Ihnen eine gute Idee geben, wie Sie Ihren eigenen Terminierungscode erstellen können.

#!/usr/bin/python 

div1 = ["Lions", "Tigers", "Jaguars", "Cougars"] 
div2 = ["Whales", "Sharks", "Piranhas", "Alligators"] 
div3 = ["Cubs", "Kittens", "Puppies", "Calfs"] 

def create_schedule(list): 
    """ Create a schedule for the teams in the list and return it""" 
    s = [] 

    if len(list) % 2 == 1: list = list + ["BYE"] 

    for i in range(len(list)-1): 

     mid = int(len(list)/2) 
     l1 = list[:mid] 
     l2 = list[mid:] 
     l2.reverse()  

     # Switch sides after each round 
     if(i % 2 == 1): 
      s = s + [ zip(l1, l2) ] 
     else: 
      s = s + [ zip(l2, l1) ] 

     list.insert(1, list.pop()) 

    return s 


def main(): 
    for round in create_schedule(div1): 
     for match in round: 
      print match[0] + " - " + match[1] 
    print 
    for round in create_schedule(div2): 
     for match in round: 
      print match[0] + " - " + match[1] 
    print 
    for round in create_schedule(div3): 
     for match in round: 
      print match[0] + " - " + match[1] 
    print 
    for round in create_schedule(div1+div2+div3): 
     for match in round: 
      print match[0] + " - " + match[1] 
     print 

if __name__ == "__main__": 
    main() 

Answer 2

Ich mochte nur diese Einschränkungen als boolean Formel kodieren und verwende eine SAT-Solver-Lösungen zu erhalten (zum Beispiel Minisat für C++, SAT4J für Java, und man konnte sogar Sie selbst einfache Löser schreiben). Die Eingabe für diese Solver wird von DIMACS standardisiert.

Siehe auch "Eine SAT-Codierung für das soziale Golfer-Problem" und "Eine SAT-basierte Scheduler für Turnierzeitpläne" für SAT-Codierungen ähnlicher Probleme.

Answer 3

hier ist ein Schuss auf eine Implementierung

public interface ITeam 
{ 
    bool PlaysOn(DateTime date); 
    bool canPlay(ITeam); //returns true if a game between the teams is legal (played once/twice 
         //already, same different divisions and other applicable rules 
} 

IEnumerable<ITeam> teams = null; //replace with initialization 
IEnumerable<ITeams> reversed = team.Reverse(); 
IEnumerable<DateTIme> gameDays = null;//replace with initialization 
var count = teams.Count(); 

foreach(var date in gameDays) 
{ 
    for(int i = 0;i<count;i++) 
    { 
     var innerTeams = i % 2 == 0 ? teams : reversed; 
     var team = (from t in innerTeams 
        where !t.PlaysOn(date) 
        select t).First(); 
     var opp = (from t in teams 
       where !t.PlaysOn(date) && t.CanPlay(team) 
       select t).First(); 
     SetupGame(team,opp); 
    } 
} //lot of optimazation possible :) 

Ich habe nur auf dem Papier getestet, aber für mein Setup es funktioniert. 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

Answer 4

Es gibt zwei Algorithmen, eine für ungerade Teams, eine für gerade Teams, um sicherzustellen, dass das Round-Robin passiert.

Ich werde dir eine Grafik erstellen, wenn ich kann.

ODD # Teams

Der Algorithmus ist im Uhrzeigersinn alle Teams zu drehen. Wenn wir 5 Teams haben:

1 2 --> 3 1 --> 5 3 --> 4 5 --> 2 4 
3 4  5 2  4 1  2 3  1 5 
5  4  2  1  3 

An dieser Stelle haben wir einen Round-Robin abgeschlossen, wo jeder jeden einmal spielt ... die nächste Runde würde wieder ..

1 2 
3 4 
5 

EVEN # von Teams

Wenn wir eine gerade Anzahl von Teams haben, machen Sie die gleiche Rotation, außer Sie halten Team # 1 in fester Position und drehen alle anderen Teams um # 1 im Uhrzeigersinn. Also, wenn wir hatten vier Teams ..

1 2 --> 1 3 --> 1 4 
3 4  4 2  2 3 

Dieses komplette Round-Robin wäre ... das nächste Spiel würde sein ..

1 2 
3 4 

Programmatisch Es gibt ein paar Möglichkeiten, wie Sie nähern konnte Dies. Vielleicht tut der oben geschriebene Code die gleiche Sache lol ..