¿Existe un algoritmo existente para la siguiente pregunta? Si no, ¿cuál es la respuesta?

La respuesta de Jayesh Lalwani es sorprendente porque brinda una solución en forma de permutación. ¡No es obvio que una sola permutación, repetida varias veces, sea una solución! Escrito como un ciclo, su ejemplo más pequeño para 9 personas es (2 5 6 7 3 9 8 4). Funciona para cuatro eventos, pero no para cinco (nada funcionaría). ¿Por qué funciona y podemos construir otras permutaciones similares a partir de los primeros principios?

Bueno, no sé cómo responder eso. Pero sí sé cómo aplicar la fuerza bruta a un problema como este, y si su problema es pequeño, puede ser lo suficientemente bueno.

Comience para el primer evento con la agrupación natural [1 2 3 … n] [n + 1 …. 2n] [2n + 1 … 3n] … para tantos grupos y personas como tengas. Si las personas no se dividen equitativamente, siempre puedes dejar algo al final o agregar personas adicionales para que encajen. Cree una estructura de datos que registre qué personas se han agrupado con qué otras personas ya.

Ahora, para el segundo evento, recorra las personas de una en una e intente asignarlas a cada grupo disponible (un ciclo anidado). Omita un grupo si tiene a alguien con quien la persona ya ha asistido a un evento anterior o ya está lleno.

Si continúa de esta manera, es casi seguro que se atascará. Está bien, si no puede hacer una colocación, retroceda a su elección anterior y coloque a esa persona en el siguiente grupo. Si aún está atascado, retroceda una opción más, etc.

Este algoritmo es una búsqueda profunda en los posibles arreglos de las personas en grupos y eventos. Una forma de implementar el retroceso es mantener una pila de todas las elecciones que ha realizado y cuál es la siguiente opción posible en cada nivel. Si el problema es fácil de resolver, es probable que DFS salga rápidamente. Si el problema es difícil o imposible, DFS puede tener que considerar todas las posibilidades, lo que lleva mucho tiempo. Pero utilizará una cantidad de memoria limitada por el número de personas multiplicado por el número de eventos.

También puede hacer una búsqueda profunda de permutaciones, si desea encontrar otras soluciones tan elegantes como la que se ofrece.

Tenga en cuenta que con P personas y un tamaño de grupo de G, luego de los eventos E, cada persona habrá visto [matemáticas] E (G-1) [/ matemáticas] personas diferentes. Si [matemáticas] E (G-1)> P [/ matemáticas] entonces no existe solución. Si [matemática] E (G-1) = P [/ matemática] entonces es posible que pueda resolver el doble problema de descubrir cómo cada persona se reúne exactamente una vez.

Puede pensar en la asignación de grupo como una matriz, con cada fila como un grupo. Ahora, de una tarea grupal para llegar a la otra, puede elegir personas que están en las diagonales. Si sigues haciendo eso, siempre obtendrás combinaciones únicas

Permítanme demostrarlo, pero lo haré con 9 personas / 3 eventos. Mostrar una matriz de 3 × 2 es más fácil. La lógica se generalizará a cualquier tamaño de matriz. Numeremos a las personas de 1 a 9 ‘

Digamos que comienzas con

  1 2 3
 4 5 6
 7 8 9

Ahora toma la primera diagonal y ponla en la primera fila
[código]
1 2 3 1 5 9
4 5 6
7 8 9
[/código]

Toma la segunda diagonal y ponla en la primera fila
[código]
1 2 3 1 5 9
4 5 6 2 6 7
7 8 9
[/código]

Ahora el 3ro

[código]
1 2 3 1 5 9
4 5 6 2 6 7
7 8 9 3 4 8
[/código]

Ahí tienes tu próxima tarea grupal

HAZLO nuevamente y obtendrás tu 3er grupo

  1 6 8
 5 7 3
 9 2 4

¡Hecho!. Ahora intente esto en papel con 49 antes de codificar.

Para [math] n ^ 2 [/ math] personas, después del primer evento, elija x entre 1 y (n-1). (nx) las personas avanzarán al siguiente evento numerado. x personas se moverán al evento anterior.

Para 9 personas, n = 3, x = 1, los dos primeros pasan al siguiente evento, el último se mueve en la otra dirección.

  - ronda 1 |  ronda 2 |  ronda 3
 Evento 1 - 123 |  786  459
 Evento 2 - 456 |  129 |  783
 Evento 3 - 789 |  453  126

Eso te dará grupos únicos cada vez, con cada persona haciendo cada evento solo una vez.