Organización de un torneo multideportivo con 7 equipos

Dices que cada equipo debe jugar al menos una vez contra cada uno de los demás? Hagamos un pequeño diagrama con una matriz diagonal:
La primera fila y la primera columna son para numerar los equipos.
\ 1 2 3 4 5 6 7                                                                                                            
1 *                                                                                                                       
2 1 *                                                                                                                     
3 1 2 *                                                                                                                   
4 1 2 3 *                                                                                                                 
5 1 2 3 4 *                                                                                                               
6 1 2 3 4 5 *                                                                                                             
7 1 2 3 4 5 6 *                                                                                                           
El asterisco es para mostrar que un equipo no juega contra sí mismo.
Vemos que habrá 21 partidos en total. Tenemos 3 canchas. Entonces cada cancha se usará 7 veces.
Y repetimos para cada uno de los 6 deportes.
¿Eso responde a tus criterios?
Colocamos en cada cancha dos equipos que no están en otra cancha (al principio todas las canchas están libres).
Y borramos cada una de las 3 casillas después de los partidos.
Repetimos mientras haya casillas en la matriz.

hola,

Necesitas más de 6 rondas para lograr esto. En 6 rondas, cada equipo ni siquiera habrá jugado 6 veces, por lo que no habrá enfrentado a cada otro equipo. Ni habrá jugado a cada deporte.

Hola,

¿Es el objetivo encontrar qué partidos deben jugarse en cada intervalo de tiempo? El problema, por supuesto, tiene muchas simetrías, ya que con una renumeración de cualquier equipo, se puede encontrar otro calendario de partidos.

El problema tiene, evidentemente, una solución (en el peor de los casos, se puede hacer un solo partido por intervalo de tiempo entre los listados por Pierrot, es decir, 21 intervalos de tiempo).

Si omitimos la restricción de los terrenos, para resolver el problema con menos intervalos de tiempo, creo que un algoritmo voraz que registre los partidos ya jugados es suficiente. Supongo que cada partido dura un intervalo de tiempo.

• Partidos jugados = {}
• t = 0
• Mientras |Partidos jugados| != 21
  • Reiniciar equipos disponibles = {1, ..., 7}
  • Para i = 0 ... 6
    • Si i no está disponible
      • Continuar
    • Encontrar un equipo disponible j tal que ni (i, j) ni (j, i) estén en Partidos jugados
    • Si j existe:
      • Agregar (i, j) -y/o (j, i)- a Partidos jugados : el partido (i, j) se juega en el instante t
      • Eliminar i y j de los equipos disponibles
    • i ++
  • t ++

Una vez que hayas decidido los partidos, creo que puedes resolver la problemática de los juegos asociados a cada partido en una segunda etapa.

Es probable, en cualquier caso en esta instancia, que un algoritmo voraz del mismo tipo sea suficiente. En el peor de los casos, tu problema se resuelve con un ILP (Programa Lineal Entero) o un CSP (Programa de Satisfacción de Restricciones), pero eso presupone que tienes conocimientos en investigación operativa (la rama de las matemáticas que se ocupa de problemas de optimización).

Buena suerte

Todos estamos de acuerdo en que se necesitan más de 6 "rondas" para jugar todas las partidas de los 6 deportes en cuestión.
Se puede ver como un problema de análisis combinatorio.
Un equipo no puede jugar contra sí mismo. El equipo A no puede jugar contra A.
De igual manera, hay simetría. Si A juega contra B, es lo mismo que decir que B juega contra A.
Por lo tanto, hay que calcular el número de combinaciones de 2 valores entre N (aquí N vale 7).
C(7, 2) vale exactamente 21 (7!/(5!2!))
Se puede hacer una lista de estos pares de números y asegurarse de que no haya dos veces el mismo par (o su equivalente).
Dependiendo del lenguaje utilizado, podríamos tener una lista de tuplas o una matriz 2D que dé así los pares.
Aquí, tenemos suerte, 21 se divide exactamente por 3. Podemos recorrer la lista y asignar los equipos por grupos de 3 pares.
Esto hará exactamente 7 rondas de 3 partidos o campos. Y se repite para cada deporte. Así que en total 21*6 = 126 partidos o 42 rondas completas.
Supongamos que el número de equipos es 8 en lugar de 7.
El número de combinaciones será entonces C(8, 2) = (8!/(6!2!)) = 28, que no se divide por 3.
Se puede hacer como con la otra lista asignando un par a cada campo por grupo de 3 pares.
Esto hará 27 pares agrupados de 3, así que 9 rondas.
¿Y qué hacemos con el 28.º par?
Lo colocamos en el primer campo y volvemos al principio de la lista, pero pasamos al siguiente deporte.
Tendremos virtualmente una lista de 28*6 (168) partidos-pares, así que 168/3 = 56 rondas completas.
Si el número de deportes fuera 7 en lugar de 6, tendríamos un total de 28*7 = 196 partidos-pares.
En este caso, tendríamos 65 rondas completas con 3 campos y una ronda con un solo campo.

Hola,

Le propongo esta formulación ILP que espero sea completa y correcta. Se define T_max a priori (por ejemplo 24) y se verifica si el solver encuentra una solución, de lo contrario, se incrementa T_max.

Notaciones: (aquí doy los dominios de definición; para aligerar las notaciones, no los recordaré en las sumas ni en los cuantificadores de las restricciones ya que son implícitamente siempre los mismos):

• i, j: los índices de los equipos en {1...7}
• k: los índices de los deportes en {1...6}
• t: los índices del tiempo en {1...T_max}

Variables de decisión (para cada valor de i, j, k, t):

• Xijt: los equipos i y j se encuentran en el tiempo t para hacer el deporte k, con valor en {0, 1}
• Yikt: el equipo i juega el deporte k en el tiempo t, con valor en {0, 1}

Función objetivo:

• min sum_t sum_i sum(i <j) Xijt // Minimizar el número de encuentros (se quiere evitar que pares de equipos (i, j) se encuentren varias veces "por diversión")

Restricciones (lineales):

• Xiit = 0 // El equipo i no puede encontrarse a sí mismo
• Para todo i, para todo j != i, para todo t: Xijt = Xjit // Si i se encuentra con j en el tiempo t, entonces el equipo j también se encuentra con i en el tiempo t
• Para todo i, sum_k Yikt <= 1 // Cada equipo i juega a como máximo un deporte en el tiempo t
• Para todo i, para todo j != i, para todo k: Yikt + Yijt >= 2 * Xijt // Si i y j se encuentran en el instante t, entonces ambas practican el deporte k
• Para todo t: sum_i sum_(i<j) Xijt <= 3 // Como máximo 3 encuentros en cada tiempo t
• Para todo i, para todo t: sum_k Yikt <= 1 // Cada equipo i juega a como máximo 1 deporte en cada instante t
• Para todo i: sum_t sum_k Yikt >= 6 // Cada equipo i juega los 6 deportes

Implementación

Desde un punto de vista práctico, hay numerosos solvers ILP. En Python, por ejemplo, scipy proporciona una función para resolver un MILP (por lo tanto, un ILP), a saber, scipy.optimize.milp.

Existen muchos otros solvers, no solo en Python. Entre los más conocidos, se puede mencionar Ilog Cplex (de pago), Coin-OR (equivalente libre de Cplex) que se puede utilizar en C++ y Java.

Observaciones

Probablemente se pueden hacer algunas relajaciones lineales (por ejemplo, decir que los Xijt y/o los Yikt están en [0, 1] en lugar de {0, 1}) para reducir el número de variables enteras (que se vuelven de facto continuas) y así acelerar significativamente la resolución. Se espera que al hacer tal relajación siempre se encuentre una solución entera (si no es así, se vuelve a pasar al dominio discreto). Entonces vale la pena mirar scipy.optimize.linprog.

Buena suerte

A continuación se muestra un ejemplo de cómo organizar este torneo en 24 partidos, es decir, en 8 rondas:

 En la ronda 0, los equipos 0 y 1 juegan en el juego 0. En la ronda 0, los equipos 2 y 3 juegan en el juego 0. En la ronda 0, los equipos 4 y 5 juegan en el juego 0. En la ronda 1, los equipos 1 y 2 juegan en el juego 1. En la ronda 1, los equipos 3 y 4 juegan en el juego 1. En la ronda 1, los equipos 5 y 6 juegan en el juego 1. En la ronda 2, los equipos 0 y 2 juegan en el juego 2. En la ronda 2, los equipos 1 y 3 juegan en el juego 2. En la ronda 2, los equipos 4 y 6 juegan en el juego 2. En la ronda 3, los equipos 0 y 3 juegan en el juego 3. En la ronda 3, los equipos 1 y 6 juegan en el juego 3. En la ronda 3, los equipos 2 y 5 juegan en el juego 3. En la ronda 4, los equipos 0 y 4 juegan en el juego 4. En la ronda 4, los equipos 1 y 5 juegan en el juego 4. En la ronda 4, los equipos 3 y 6 juegan en el juego 4. En la ronda 5, los equipos 0 y 5 juegan en el juego 5. En la ronda 5, los equipos 1 y 4 juegan en el juego 5. En la ronda 5, los equipos 2 y 6 juegan en el juego 5. En la ronda 6, los equipos 0 y 6 juegan en el juego 0. En la ronda 6, los equipos 2 y 4 juegan en el juego 4. En la ronda 6, los equipos 3 y 5 juegan en el juego 5. En la ronda 7, los equipos 0 y 6 juegan en el juego 1. En la ronda 7, los equipos 2 y 4 juegan en el juego 3. En la ronda 7, los equipos 3 y 5 juegan en el juego 2.