Buenos arreglos de asientos para la secuencia de comidas y mesas de tamaño k para un grupo de personas

Dado un conjunto de personas, me gustaría sentarlas para una secuencia de comidas en mesas de tamaño k . (Por supuesto, hay suficientes mesas para sentarse todas | S | para cada comida.) Me gustaría organizar esto de tal manera que nadie comparta una mesa con la misma persona dos veces. Los valores típicos son | S | = 45 y k = 5 y 6 a 10 comidas.$S$$k$$|S|$$|S|=45$$k=5$

Dicho de manera más abstracta, me gustaría encontrar una secuencia de particiones de manera que cada partición consista en subconjuntos de cardinalidad k separados por pares y la propiedad global agregada de que cualquier intersección entre dos de estos subconjuntos no contiene más de un elemento. Sospecho que esto puede formularse como un problema teórico o combinatorio gráfico.$S$$k$

Le agradecería una mejor formulación del problema y sugerencias para la literatura relevante, ya que está fuera de mi dominio.

El trasfondo: esto podría usarse para la disposición de los asientos en Schloss Dagstuhl, donde muchos informáticos vienen a discutir su investigación en el transcurso de una semana. Actualmente, los asientos se realizan al azar y, como era de esperar, algunas personas se encuentran sentadas con las mismas personas dos veces (o más a menudo) en el transcurso de una semana. También, como era de esperar, recibimos algunas quejas sobre esto y sugerencias vagas sobre cómo mejorar esto. Me gustaría entender esto mejor. Una formulación más sólida del problema implica optimizar quién está sentado uno al lado del otro, pero creo que esto no es relevante para las tablas de tamaño 5.

Fuera de la aplicación, creo que la pregunta interesante es la cantidad máxima de comidas que se pueden servir para un y k dado , es decir, cuántas particiones existen.$S$$k$

Aquí hay una variante de la respuesta original (a continuación) que proporciona la configuración deseada: tablas de tamaño 5, 45 personas y 10 comidas, excepto que una comida tiene algunas tablas de tamaño 4.

Sea el campo de tamaño 9. Elija 4 líneas verticales y degeneradas { ( b , x ) | x ∈ F } por cada b = 0 , 1 , 2 , 3 y declara a su gente "vacía". Nos quedan 81 - 9x4 = 45 personas.$F$$\{(b,x) | x \in F\}$$b = 0,1,2,3$

9 comidas se dan por pendientes . Las intersecciones con las 4 líneas degeneradas vacías reducen el tamaño de la tabla a 9-4 = 5.$a = 0,1,\ldots,8$

Las líneas degeneradas restantes dan una comida adicional. x ∈ F } para cada b = 4 , 5 , 6 , 7 , 8 . Aquí el tamaño de la tabla es 9. Sin embargo (en cualquier solución) podemos dividir una tabla de tamaño 9 en una tabla de tamaño 5 y una de tamaño 4.$\{(b,x) | x \in F\}$$b = 4,5,6,7,8$

Si hay algunas personas más, se puede usar el campo de tamaño 11.

$k^2$$k$

$F$$k$$F \times F$

$a$$k$$\{(x,ax+b) | x \in F\}$$b \in F$

La propiedad de intersección que desea es el hecho de que las líneas con pendientes distintas se cruzan exactamente en un punto.

$2k^2$$k^2$$2k^2 - k = 45$$\{(x,x)|x\in F\}$$k-1$

Para más comidas uno podría, por ejemplo, elegir una partición diferente en dos grupos al comienzo de la sexta comida. (Digamos que intercala la partición original, para asegurarse de que los dos grupos "se mezclan"). Aunque, por supuesto, esto puede dar lugar a algunas intersecciones.

Aquí hay un límite superior (¿suelto?) En la cantidad de comidas que puede servir.

$|S| = n$$n$$k$$n/k$

$S$$n/k$$k$$\Theta(nk)$

$n$$\Theta(n^2)$$O(n/k)$

$\frac{n-1}{k-1}$

Si desea que dos personas se sienten en la misma mesa exactamente una vez, esto se llama diseño 2 resoluble y se ha estudiado mucho. Por supuesto, dejar pasar algunas comidas daría una solución a su problema cuando dos personas pueden reunirse como máximo una vez. (Pero supongo que pueden existir otras soluciones).

No estoy seguro de si necesita un algoritmo determinista, pero he resuelto un problema similar en el pasado usando un método de Monte Carlo en cadena de Markov .

Puede ver un ejemplo práctico de este enfoque en Github : este programa intenta sentar a un grupo de personas en mesas de un tamaño fijo, dado un conjunto de restricciones de asientos que pueden ser positivas o negativas ("must" o "must not" ), y absoluto o relativo ("preferible").

Nota: este programa no resuelve exactamente el mismo problema que usted propone, pero ofrece una demostración funcional del método Monte Carlo de la cadena Markov, y está lo suficientemente cerca como para que pueda ajustarlo fácilmente según sea necesario para su problema.

El programa resuelve el problema para una cena, pero en su caso, una forma fácil de abordar el problema sería ejecutar el algoritmo una vez para cada cena, proporcionando cada vez los acompañantes anteriores de cada comensal como requisitos difusos o absolutamente negativos. (La ventaja de los requisitos difusos es que tiene la garantía de que el algoritmo se detendrá en todas las entradas, incluso si no se puede encontrar una disposición perfecta).

En este proceso, primero intentaremos sentar a cada comensal de acuerdo con los requisitos absolutos; es posible que desee omitir esta parte del proceso, ya que solo funciona cuando los requisitos absolutos son relativamente pequeños; de lo contrario, terminas con un problema increíblemente grande .

En el siguiente paso, creamos una serie de tablas y asignamos aleatoriamente a los participantes a las tablas para una configuración inicial, y se calcula una puntuación para representar el número de requisitos difusos que se han satisfecho. Los pares de comensales se cambian aleatoriamente, y la puntuación se vuelve a calcular para esas tablas para determinar si la nueva configuración es preferible.

Idealmente, esta parte del proceso debería repetirse con varias configuraciones iniciales, y puede calcularse fácilmente en paralelo.

Creo que cualquier disposición de asientos válida es equivalente a una hipergrafía d-regular en | S | vértices, donde d es el número de cenas, con un rango máximo de k y máximo codegree 1. La solución trivial es hacer que todos siempre se sienten solos, pero supongo que el objetivo es minimizar el número de mesas.