Cómo generar automáticamente un horario de liga deportiva

Question

Comenzaré diciendo que entiendo que este tema es complicado y que probablemente no haya una respuesta fácil. Si fuera fácil, todos lo estarían haciendo. Dicho esto ...

Me han pedido que cree una aplicación para administrar una liga deportiva. La mayoría de los conceptos son bastante fáciles de entender, excepto este: Cómo generar un horario de juego donde no hay superposiciones (el equipo juega 2 equipos a la vez), donde un equipo en una división juega dos veces con sus equipos pero juega con equipos del otras divisiones una vez, y se asegura de que no haya agujeros en el calendario (cada equipo juega todas las semanas)

En este momento, el proceso se realiza manualmente utilizando una hoja de cálculo tipo piedra de rosetta que he creado para cumplir este propósito, pero solo funciona para la cantidad de equipos para los que fue diseñada. Tengo variaciones hechas para 30 equipos, 24 equipos y 28 equipos. En lugar de intentar continuamente reajustar mi tabla de traducción, me gustaría poder codificar esa lógica y modificar ese proceso en su lugar.

¿Pensamientos?

Answer 1

Hay un sistema bastante sencillo que se utiliza en, p. torneos de ajedrez llamados round-robin.

La idea es dividir a los jugadores en los dos lados de una mesa. Uno de los jugadores está designado como un "centro" (por falta de una palabra mejor). El torneo comienza con jugadores enfrentados que juegan uno contra el otro. Después de la primera ronda, todos menos el centro mueven una silla hacia adelante y se cambia el orden blanco / negro (en casa / fuera en deportes). Toda la competencia de todos contra todos termina cuando los jugadores se sientan en sus lugares originales. Si quieres que todos jueguen a todos dos veces, haz lo mismo de nuevo.

Artículo de Wikipedia con detalles de implementación.

En su caso especial, intentaría hacer el round robin una vez, incluidos todos los equipos. Luego, hace lo mismo para cada división una vez y para asegurarse de que los equipos dentro de las divisiones jueguen entre sí una vez en casa y una vez fuera, verifique desde el primer round robin cómo jugaron los equipos en esa ronda.

La desventaja de esto es, por supuesto, que jugarás todos los partidos entre divisiones mucho antes de que finalice el torneo (dado que los últimos partidos n-1 son contra equipos intra-división [n = número de equipos en la división ]). Si esto es un problema, simplemente puede cambiar las coincidencias un poco.

En realidad escribí un script simple de Python que hace esto. No tomó muchas líneas de código y produjo muy buenos resultados. Esto creará un cronograma donde cada equipo juega contra cada equipo en su división dos veces y una vez contra equipos en otras divisiones. Sin embargo, no hay verificación para asegurarse de que los equipos se reúnan dos veces de tal manera que el mismo equipo esté en casa. Pero este código debería dar una buena idea sobre cómo crear su propio código de programación.

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

Hay dos algoritmos, uno para equipos impares, uno para equipos pares para asegurarse de que ocurra el round robin.

Voy a generar un gráfico si puedo.

ODD # de equipos

El algoritmo es rotar todos los equipos en sentido horario. Si tuviéramos 5 equipos:

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   

En este punto, hemos completado un round robin donde todos juegan entre sí una vez ... la próxima ronda sería nuevamente ...

1 2
3 4
5

INCLUSO # de equipos

Cuando tenemos un número par de equipos, usted hace la misma rotación, excepto que mantiene el equipo # 1 en posición fija y gira a todos los otros equipos alrededor del # 1 en sentido horario. Entonces, si tuviéramos 4 equipos ...

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

Este sería un round robin completo ... el próximo partido sería ...

1 2 
3 4 

Programáticamente, hay algunas maneras de abordar esto. Tal vez el código publicado anteriormente hace lo mismo jajaja.

Answer 3

Simplemente codificaría estas restricciones como una fórmula booleana y usaría algún solucionador SAT para obtener soluciones (por ejemplo, MiniSAT para C ++, SAT4J para Java, e incluso podría escribir su propio solucionador simple). La entrada a estos solucionadores está estandarizada por DIMACS.

Ver también " Una codificación SAT para el problema del golfista social " y "Un programador basado en SAT para horarios de torneos" para codificaciones SAT de problemas similares.

Answer 4

aquí hay una oportunidad para una implementación

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

Solo lo probé en papel, pero para mi configuración funciona. Alternando entre comenzar al principio de la lista de equipos y al final de la lista, evito las situaciones en las que el mismo equipo tendría que jugar el mismo equipo una y otra vez (o jugar repetidamente el mismo día) en mi prueba de papel I representaba cada encuentro posible como un oponente diferente, pero eso es básicamente lo que debería hacer el método CanPlay. Espero que esto ayude, aunque no sea una solución completa