¿Cómo dividir una lista en listas más pequeñas para que las probabilidades de que un elemento se encuentre con otro se distribuyan uniformemente?

Question

Estoy luchando con un algoritmo para dividir un grupo de concursantes en grupos más pequeños para hacer rondas. Tomemos por ejemplo un grupo de $20$ personas, que quiero dividir en $3$ grupos $(7,7,6).$ En cada ronda del concurso, los grupos son diferentes, de modo que todos tienen que combatir a todos los demás en una distribución bastante justa.

El problema es que con una selección aleatoria (ingenua) una persona tiene que combatir más a la misma persona que otra. Es decir, dos elementos acaban a menudo en el mismo grupo.

Me gustaría hacer esto más justo para que para un número dado de concursantes, tamaño de grupo (no todos los grupos son del mismo tamaño) y número de rondas, el algoritmo encuentre un conjunto justo de grupos por ronda para que en promedio cada concursante tenga las mismas probabilidades de encontrarse con el mismo concursante durante las rondas.

¿Existe alguna literatura sobre este tema que pueda consultar? ¿O algún algoritmo conocido?

Answer 1

Está claro que el equilibrio perfecto no es alcanzable en todos los casos: supongamos que se hacen cuatro rondas para cuatro personas en dos grupos, entonces todo el mundo tiene que jugar con un oponente al menos dos veces y con otro como máximo una vez. Así que ahora podemos discutir qué es exactamente un objetivo alcanzable.

Considere para cada par de personas el número de rondas en las que están en el mismo grupo (es decir, el número de veces que juegan entre sí). Queremos que este conjunto múltiple $S$ de los números para que se componga de números cercanos entre sí. Podríamos, por ejemplo, tratar de tener $\max S - \min S \leq 1$ (es decir, si $A$ juega $B$ $n$ veces, entonces $C$ juega $D$ como máximo $n + 1$ y al menos $n - 1$ veces). (Advertencia: en este momento no tengo claro que esto sea siempre posible). O podríamos intentar que la varianza del $S$ sea mínimo. Por último, podríamos intentar minimizar la varianza con la condición min / max.

Si los grupos fueran del mismo tamaño, entonces podría utilizar diseños de bloques para lograr un equilibrio perfecto (donde $S$ es constante) para algunos conjuntos de parámetros. Por lo demás, sin embargo, creo que no hay ninguna teoría que dé una solución exacta a este problema. Es muy posible que la forma más práctica de resolverlo sea utilizando un meta-heurística como Recocido simulado o Búsqueda Tabu .