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 harían. Dicho esto ...

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

Ahora el proceso se hace manualmente usando una hoja de cálculo tipo rosetta stone que he creado para cumplir este propósito, pero solo funciona para la cantidad de equipos para los que fue diseñado. 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.

¿Pensamientos?

Answer 1

Hay un sistema bastante sencillo utilizado en, por ejemplo, torneos de ajedrez llamados round-robin.

La idea es dividir a los jugadores en los dos lados de una mesa. Uno de los jugadores se designa como "hub" (por falta de una palabra mejor). El torneo comienza por tener jugadores enfrentados que juegan uno contra el otro. Después de la primera ronda, todos menos el cubo mueven una silla hacia adelante y se cambia el orden blanco/negro (inicio/fuera en deportes). La competencia completa de round-robin finaliza cuando los jugadores se sientan en sus lugares originales. Si quieres que todos jueguen a todos dos veces, haz lo mismo otra vez.

Wikipedia article con detalles de implementación.

En su caso especial trataría de hacer el round robin una vez, incluyendo todos los equipos. Luego, haga lo mismo para cada división una vez y para asegurarse de que los equipos dentro de las divisiones se jueguen entre sí una vez en casa y una vez fuera, verifique desde la primera ronda el rumbo que 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 (ya que las últimas n-1 son contra equipos intradivisión [n = número de equipos en división]). Si esto es un problema, simplemente podría cambiar las coincidencias un poco.

De hecho, escribí un script de Python simple que hace esto. No tomó muchas líneas de código y produjo muy buenos resultados. Esto creará un cronograma donde cada equipo jugará a cada equipo en su división dos veces y una vez contra equipos en otras divisiones. Sin embargo, no existe un control 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

me acaba de codificar estas restricciones como una fórmula booleana y utilizar algunos SAT-solucionador para obtener soluciones (por ejemplo MINISAT para C++, Java SAT4J para, e incluso se podría escribir que poseen solucionador simple). La entrada a estos solucionadores está estandarizada por DIMACS.

Vea también "Una codificación SAT para el problema del golfista social" y "Programador basado en SAT para horarios de torneo" para codificaciones SAT de problemas similares.

Answer 3

Aquí hay una foto en una aplicació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 :) 

Yo lo he probado sólo en el papel, pero para mi configuración funciona. Al alternar entre comenzar al principio de la lista de equipos y al final de la lista evito las situaciones en las que el mismo equipo debería jugar el mismo equipo una y otra vez (o jugar repetidamente el mismo día) en mi prueba de papel I representó 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 es una solución completa

Answer 4

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 consiste en hacer girar todos los equipos de las agujas del reloj. 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 siguiente ronda sería otra vez ..

1 2 
3 4 
5 

AÚN # de equipos

Cuando tenemos un número par de equipos, usted hace la misma rotación, excepto que mantiene al equipo n. ° 1 en posición fija y gira todos los otros equipos alrededor del n. ° 1 en el sentido de las agujas del reloj. Por lo tanto, si tuviéramos 4 equipos ..

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

Este sería uno de round robin completa ... hasta el siguiente partido sería ..

1 2 
3 4 

mediante programación, hay algunas maneras que usted puede acercarse a esta. Tal vez el código publicado arriba haga lo mismo, lol ...