So generieren Sie automatisch einen Sport -League -Zeitplan

Question

Ich werde zunächst sagen, dass ich verstehe, dass dieses Thema kompliziert ist und dass es wahrscheinlich keine einfache Antwort gibt. Wenn es einfach wäre, würde es jeder tun. Davon abgesehen ...

Ich wurde gebeten, eine Bewerbung zur Verwaltung einer Sportliga zu erstellen. Die meisten Konzepte sind ziemlich leicht zu verstehen, bis auf dieses Andere Abteilungen einmal und stellt sicher, dass der Zeitplan keine Löcher enthält (jedes Team spielt jede Woche)

Derzeit wird der Prozess manuell mit einer Tabelle vom Typ Rosetta -Stein manuell durchgeführt, die ich für diesen Zweck erstellt habe, aber es funktioniert nur für die Anzahl der Teams, für die es konzipiert wurde. Ich habe Variationen für 30 Teams, 24 Teams und 28 Teams. Anstatt kontinuierlich zu versuchen, meine Übersetzungstabelle neu anzupassen, möchte ich diese Logik kodifizieren und diesen Prozess stattdessen optimieren.

Gedanken?

Answer 1

Es gibt ein ziemlich unkompliziertes System, das bei z. B. Schachturnieren genannt wird, die als Round-Robin bezeichnet werden.

Die Idee ist, die Spieler auf die beiden Seiten eines Tisches zu teilen. Einer der Spieler ist als "Hub" bezeichnet (aus einem besseren Wort). Das Turnier beginnt damit, dass die Spieler gegeneinander gegenüberstehen. Nach der ersten Runde, aber der Hub bewegt einen Stuhl nach vorne und die Bestellung von Weiß/Schwarz (nach Hause/Auswärts im Sport) wird umgeschaltet. Der gesamte Round-Robin-Wettbewerb ist beendet, wenn die Spieler an ihren ursprünglichen Orten sitzen. Wenn Sie möchten, dass alle zweimal alle spielen, tun Sie einfach das Gleiche.

Wikipedia -Artikel mit Implementierungsdetails.

In Ihrem Sonderfall würde ich versuchen, den Round Robin einmal mit allen Teams zu machen. Dann tun Sie dasselbe für jede Division einmal und um sicherzustellen, dass die Teams in Divisionen einmal zu Hause und einmal weg spielen. Überprüfen Sie die erste Robin von Robin, wie die Teams in dieser Runde gespielt haben.

Die Herunterseite davon ist natürlich, dass Sie alle Zwischen-Division-Spiele lange vor dem Abschluss des Turniers spielen werden (da die letzten N-1-Spiele gegen Intra-Division-Teams [n = Anzahl der Teams in der Division] sind). Wenn dies ein Problem ist, können Sie einfach ein bisschen Spiele austauschen.

Ich habe tatsächlich ein einfaches Python -Skript geschrieben, das dies tut. Es dauerte nicht viele Codezeilen und lieferte ziemlich gute Ergebnisse. Dadurch wird ein Zeitplan erstellt, in dem jedes Team jedes Team in seiner Division zweimal und einmal gegen Teams in anderen Abteilungen spielt. Es gibt jedoch keine Überprüfung, um sicherzustellen, dass sich die Teams zweimal so treffen, dass das gleiche Team zu Hause ist. Dieser Code sollte jedoch eine gute Vorstellung davon geben, wie Sie Ihren eigenen Planungscode 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

Es gibt zwei Algorithmen, eine für ungerade Teams, eine für selbst Teams, um sicherzustellen, dass der Round Robin stattfindet.

Ich werde Ihnen eine Grafik erzeugen, wenn ich kann.

Ungerade Anzahl der Teams

Der Algorithmus soll alle Teams im Uhrzeigersinn drehen. Wenn wir 5 Teams hätten:

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   

Zu diesem Zeitpunkt haben wir einen Round Robin abgeschlossen, in dem sich alle einmal spielen ... die nächste Runde wäre wieder ..

1 2
3 4
5

Sogar die Anzahl der Teams

Wenn wir eine gleichmäßige Anzahl von Teams haben, führen Sie die gleiche Rotation durch, außer dass Sie Team Nr. 1 in fester Position halten und alle anderen Teams um Nr. 1 im Uhrzeigersinn drehen. Also, wenn wir 4 Teams hatten.

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

Dies wäre ein komplettes Rund -Robin ... das nächste Match wäre ..

1 2 
3 4 

Programmatisch gibt es einige Möglichkeiten, wie Sie dies nähern können. Vielleicht macht der oben gepostete Code das Gleiche lol ..

Answer 3

Ich würde diese Einschränkungen nur als Boolesche Formel codieren und einen Sat-Solver verwenden, um Lösungen zu erhalten (z. B. Minisat für C ++, SAT4J für Java, und Sie könnten Ihnen sogar einen eigenen einfachen Solver schreiben). Der Eingang zu diesen Löser wird durch DIMACS standardisiert.

Siehe auch "Eine SAT-Codierung für das Problem des sozialen Golfers" und "Ein SAT-basierter Scheduler für Turnierpläne" für SAT-Codings ähnlicher Probleme.

Answer 4

Hier ist ein Schuss bei einer 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 es nur auf Papier getestet, aber für mein Setup funktioniert es. Durch die Abwechslung zwischen Beginn der Teamsliste und dem Ende der Liste meide ich die Situationen, in denen das gleiche Team immer wieder dasselbe Team spielen müsste (oder wiederholt am selben Tag spielen) in meinem Papiertest i stellte jede mögliche Begegnung als einen anderen Gegner dar, aber das sollte die CanPlay -Methode im Grunde genommen tun. Ich hoffe, das hilft, obwohl es keine vollständige Lösung