2 votos

Juegos de programación de problemas de permutación

Lo hay:

  • 14 equipos $t$ numerados del 0 al 13
  • 13 juegos diferentes $g$ numerados del 0 al 12
  • 13 rondas $r$ numerados del 0 al 12

Quiero hacer una planificación así:

  • cada equipo juega contra el otro equipo
  • cada equipo juega los 13 partidos
  • No se permite jugar 2 veces el mismo juego durante una ronda

¿Existe una forma eficaz de construir esa planificación?

¿Existe una forma de definir una función "simple" $f(t,r)$ que devuelve el juego $g $ jugado por el equipo t en la ronda r.

Me interesa más la forma de enfocar el problema que la solución real.

5voto

Shabaz Puntos 403

Sí, los jugadores de bridge lo llaman movimiento Howell. Puede ver este ejemplo en particular en este sitio o este sitio . Sus juegos son los pares de tablas. Básicamente, 13 de las parejas (tus equipos) se mueven en una dirección por la sala (la otra está quieta) y los tableros se mueven en la otra dirección por la sala. La cosa se complica si el número de equipos es 4n o 4n-1.

Puedes pensar en sentar a los equipos en una mesa larga. El equipo de un extremo está fijo y el resto va rotando. Cada equipo juega contra el equipo del otro lado de la mesa. Los partidos rotan alrededor de los partidos, en el sentido contrario de los equipos, con una pila sentada que no se juega (sólo se juegan 7 en cada ronda).

Tenga en cuenta que sus partidas y rondas deben estar numeradas del 0 al 12 o del 1 al 13.

2voto

David Spencer Puntos 491

Utilizando el método de rotación con un jugador fijo en la respuesta de Ross Millikan o en http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm Creo que podemos escribir una función explícita para generar estos emparejamientos.

Empecé probando el caso más pequeño de $8$ equipos. Considere la siguiente configuración inicial:

7 6 5 4
0 1 2 3

Equipo de retención $7$ fijos y girando todos los demás en el sentido de las agujas del reloj, nos encontramos con la siguiente lista de emparejamientos:

             Round number (r)
           0  1  2  3  4  5  6
           -------------------
        0| 7  2  4  6  1  3  5
        1| 6  7  3  5  0  2  4
        2| 5  0  7  4  6  1  3
 Team   3| 4  6  1  7  5  0  2
  (t)   4| 3  5  0  2  7  6  1
        5| 2  4  6  1  3  7  0
        6| 1  3  5  0  2  4  7
        7| 0  1  2  3  4  5  6

El patrón es evidente. Equipo $7$ El adversario del presidente es sencillamente $r$ . Para todos los demás, la ronda $0$ oponente es $7-t$ y en las siguientes rondas el oponente incrementa en $2$ cada vez (con la excepción de la ronda que por ese patrón tendría un equipo que se juega a sí mismo, durante la cual el equipo juega al equipo $7$ en su lugar).

La función es:

$$f(t, r, n) = \left\{ \begin{array}{lr} n - 1 & : t = r\\ r & : t = n - 1\\ (2*r - t)\bmod{(n-1)} : \hspace{10 mm} t\neq r\hspace{4 mm} \And \hspace{4 mm} t\neq n - 1\\ \end{array} \right.$$

donde $t$ es el número del equipo, $r$ es un número redondo, y $n$ es el número de equipos. La función está definida para los enteros positivos pares $n$ , entero no negativo $t$ donde $t<n$ y un número entero no negativo $r$ donde $r<n-1$ .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X