Comment générer automatiquement un calendrier de ligue sportive

Question

Je commencerai par dire que je comprends que ce sujet est compliqué et qu'il n'y a probablement pas de réponse facile. Si c'était facile, tout le monde le ferait. Cela étant dit ...

On m'a demandé de créer une application pour gérer une ligue sportive. La plupart des concepts sont assez faciles à comprendre, à l’exception de celui-ci: comment générer un calendrier de jeu ne se chevauchant pas (une équipe joue contre deux équipes à la fois), où une équipe d’une division joue deux fois avec ses équipes autres divisions une fois et veille à ce qu’il n’y ait pas de trous dans l’horaire (chaque équipe joue chaque semaine)

À l’heure actuelle, le processus est effectué manuellement à l’aide d’un tableur rosetta stone que j’ai construit dans ce but, mais il ne fonctionne que pour le nombre d’équipes pour lequel il a été conçu. J'ai des variations faites pour 30 équipes, 24 équipes et 28 équipes. Plutôt que d'essayer continuellement de réajuster ma table de traduction, j'aimerais pouvoir codifier cette logique et peaufiner ce processus.

Pensées?

Answer 1

Il existe un système assez simple utilisé, par exemple. tournois d’échecs appelés round-robin.

L’idée est de diviser les joueurs des deux côtés d’une table. L'un des joueurs est désigné comme "concentrateur". (pour un meilleur mot). Le tournoi commence par la confrontation des joueurs. Après le premier tour, tout le monde, sauf le moyeu, avance d'une chaise et l'ordre blanc / noir (domicile / extérieur en sport) est inversé. La ronde préliminaire est terminée lorsque les joueurs sont assis à leur place d'origine. Si vous voulez que tout le monde joue deux fois, faites de nouveau la même chose.

Article Wikipedia avec les détails de la mise en œuvre.

Dans votre cas particulier, j'essaierais de faire le tournoi à la ronde une fois en incluant toutes les équipes. Ensuite, vous faites la même chose pour chaque division une fois et pour vous assurer que les équipes au sein des divisions se jouent une fois à la maison et une fois à l'extérieur, vérifiez dès le premier tour comment les équipes ont joué lors de ce tour.

L’inconvénient, c’est bien entendu que vous jouerez tous les matchs inter-divisions bien avant la fin du tournoi (étant donné que les n-1 derniers matchs sont opposés à des équipes intra-division [n = nombre d’équipes de la division ]). Si cela pose problème, vous pouvez simplement échanger des correspondances un peu.

J'ai en fait écrit un simple script Python qui fait cela. Cela n'a pas pris beaucoup de lignes de code et a produit de très bons résultats. Cela créera un calendrier dans lequel chaque équipe affrontera chaque équipe de sa division deux fois et une fois contre des équipes appartenant à d'autres divisions. Il n'y a aucune vérification pour s'assurer que les équipes se rencontrent deux fois de telle sorte que la même équipe est à la maison, cependant. Mais ce code devrait donner une bonne idée sur la façon de créer votre propre code de planification.

#!/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

Il existe deux algorithmes, un pour les équipes impaires et un pour les équipes paires afin de s’assurer que le tournoi à la ronde se produit.

Je vais vous générer un graphique si je peux.

Nombre ODD d'équipes

L'algorithme consiste à faire pivoter toutes les équipes dans le sens des aiguilles d'une montre. Si nous avions 5 équipes:

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   

À ce stade, nous avons terminé un tournoi à la ronde où tout le monde se joue une fois ... le prochain tour serait à nouveau ..

1 2
3 4
5

MÊME nombre d'équipes

Lorsque nous avons un nombre pair d’équipes, vous faites la même rotation, sauf que vous tenez l’équipe n ° 1 en position fixe et faites pivoter toutes les autres équipes autour de la n ° 1 dans le sens des aiguilles d’une montre. Donc, si nous avions 4 équipes ..

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

Ce serait un round robin complet ... le prochain match serait ..

1 2 
3 4 

Par programmation, il y a quelques façons d’aborder ceci. Peut-être que le code affiché ci-dessus fait la même chose lol ..

Answer 3

Je voudrais simplement encoder ces contraintes sous forme de formule booléenne et utiliser un solveur SAT pour obtenir des solutions (par exemple, MiniSAT pour C ++, SAT4J pour Java, et vous pourriez même écrire votre propre solutionneur simple). L’entrée de ces solveurs est normalisée par DIMACS.

Voir aussi "Encodage SAT pour le problème du golfeur social" et "Un agenda basé sur SAT pour les horaires de tournoi" pour le codage SAT de problèmes similaires.

Answer 4

voici un coup à une implémentation

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 :)

Je ne l'ai testé que sur papier, mais pour ma configuration, cela fonctionne. En alternant entre le début de la liste des équipes et la fin de la liste, j'évite les situations dans lesquelles une même équipe serait obligée de jouer à plusieurs reprises avec la même équipe (ou de jouer plusieurs fois le même jour) dans mon test de papier I représentait chaque rencontre possible comme un opposant différent, mais c’est ce que la méthode CanPlay devrait faire. J'espère que cela vous aidera, même si ce n'est pas une solution complète