Bonne disposition des sièges pour la séquence des repas et des tables de taille k pour un groupe de personnes

Étant donné un ensemble $S$ de personnes, je voudrais les asseoir pour une séquence de repas à des tables de taille $k$ . (Bien sûr, il y a suffisamment de tables pour asseoir tous les $|S|$ pour chaque repas.) J'aimerais organiser cela de telle sorte que personne ne partage une table avec la même personne deux fois. Les valeurs typiques sont $|S|=45$ et $k=5$ et 6 à 10 repas.

De manière plus abstraite, j'aimerais trouver une séquence de partitions de $S$ telle que chaque partition se compose de sous-ensembles disjoints de cardinalité $k$ et de la propriété globale ajoutée que toute intersection entre deux de ces sous-ensembles ne contient pas plus d'un élément. Je soupçonne que cela peut être formulé comme un problème théorique ou combinatoire de graphes.

Je serais reconnaissant pour une meilleure formulation du problème et des pointeurs vers la littérature pertinente car elle est en dehors de mon domaine.

Le contexte: cela pourrait être utilisé pour la disposition des sièges au Schloss Dagstuhl où de nombreux informaticiens viennent discuter de leurs recherches au cours d'une semaine. Actuellement, l'assise se fait au hasard et sans surprise, certaines personnes se retrouvent assis avec les mêmes personnes deux fois (ou plus souvent) au cours d'une semaine. Sans surprise, nous recevons quelques plaintes à ce sujet et de vagues suggestions sur la façon de l'améliorer. J'aimerais mieux comprendre cela. Une formulation plus forte du problème implique d'optimiser qui est assis côte à côte, mais je pense que cela n'est pas pertinent pour les tableaux de taille 5.

En dehors de l'application, je pense que la question intéressante concerne le nombre maximum de repas pouvant être servis pour un et un k donnés , c'est-à-dire combien de telles partitions existent.$S$$k$

Voici une variante de la réponse originale (ci-dessous) qui donne le réglage souhaité: des tables de taille 5, 45 personnes et 10 repas, sauf qu'un repas a quelques tables de taille 4.

Soit le champ de taille 9. Choisissez 4 lignes verticales dégénérées { ( b , x ) | x $F$ pour chaque b = 0 , 1 , 2 , 3 et déclarer leur peuple "vide". Il nous reste 81 - 9x4 = 45 personnes.$\{(b,x) | x \in F\}$$b = 0,1,2,3$

9 repas sont donnés par pistes . Les intersections avec les 4 lignes dégénérées vides réduisent la taille du tableau à 9-4 = 5.$a = 0,1,\ldots,8$

Un repas supplémentaire est donné par les lignes dégénérées restantes pour chaque b = 4 , 5 , 6 , 7 , 8 . Ici, la taille du tableau est 9. Cependant (dans toute solution), nous pouvons diviser un tableau de taille 9 en un tableau de taille 5 et un de taille 4.$\{(b,x) | x \in F\}$$b = 4,5,6,7,8$

S'il y a encore quelques personnes, on peut utiliser le champ de taille 11.

Tout d' abord nous traitons personnes et k repas.$k^2$$k$

Choisissez un champ fini de taille k et identifierpersonnes avec F × F . A chaque repas correspond une pente, à une table une ligne parallèle à cette pente.$F$$k$$F \times F$

Plus précisément, le repas a k tables { ( x , a x + b $a$$k$ pour chaque b ∈ F .$\{(x,ax+b) | x \in F\}$$b \in F$

La propriété d'intersection que vous souhaitez est le fait que les lignes avec des pentes distinctes se coupent en un seul point.

Pour gérer personnes, divisez-les en deux groupes de k 2 chacun et appliquez la construction ci-dessus à chaque groupe. Pour gérer 2 k 2 - k = 45 , étiquetez (dans le premier groupe) une ligne fixe telle que { ( x , x ) | x ∈ F } comme "vide". Vous pouvez avoir quelques tables avec k - 1 personnes.$2k^2$$k^2$$2k^2 - k = 45$$\{(x,x)|x\in F\}$$k-1$

Pour plus de repas, on pourrait par exemple choisir une partition différente en deux groupes au début du 6ème repas. (Supposons que vous entrelaciez la partition d'origine, pour vous assurer que les deux groupes «se mélangent».) Bien sûr, cela peut entraîner des intersections.

Voici une limite supérieure (lâche?) Du nombre de repas que vous pouvez servir.

Soit et supposons que n est divisible par k . Supposons également que vous avez exactement $|S| = n$$n$$k$ tables et que vous souhaitez que chaque table soit pleine à chaque repas.$n/k$

Pour chaque repas, construisez un graphique avec un nœud pour chaque personne en et un bord lorsque deux personnes partagent une table. Ce graphique est une collection de n / k cliques de taille k chacune . Ainsi, le nombre d'arêtes dans le graphique est Θ ( $S$$n/k$$k$ .$\Theta(nk)$

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

$\frac{n-1}{k-1}$ , qui, pour vos valeurs typiques, est 11.

Si vous voulez que deux personnes s'assoient à la même table exactement une fois, alors cela s'appelle un design 2 résolvable et a été beaucoup étudié. Bien sûr, permettre de sauter quelques repas donnerait une solution à votre problème lorsque deux personnes peuvent se rencontrer au plus une fois. (Mais d'autres solutions pourraient exister, je suppose.)

Je ne sais pas si vous avez besoin d'un algorithme déterministe, mais j'ai résolu un problème similaire dans le passé en utilisant une méthode Monte Carlo à chaîne de Markov .

Vous pouvez voir un exemple de travail de cette approche sur Github - ce programme tente de placer un groupe de personnes à des tables d'une taille fixe, étant donné un ensemble de contraintes de sièges qui peuvent être positives ou négatives ("doit" ou "ne doit pas" ), et absolu ou relatif ("préférable").

Remarque: ce programme ne résout pas exactement le même problème que vous proposez, mais il donne une démonstration de travail d'une méthode Monte Carlo de chaîne de Markov, et il est suffisamment proche pour que vous puissiez facilement l'ajuster en fonction de votre problème.

Le programme résout le problème pour un dîner, mais dans votre cas, un moyen facile d'aborder le problème serait d'exécuter l'algorithme une fois pour chaque dîner, en fournissant à chaque fois les compagnons précédents de chaque dîner en tant qu'exigences floues ou absolues négatives. (L'avantage des exigences floues est que vous êtes assuré que l'algorithme s'arrêtera sur toutes les entrées, même si un arrangement parfait ne peut pas être trouvé).

Dans ce processus, nous tenterions d'abord de placer chaque salle à manger selon les exigences absolues - vous voudrez peut-être ignorer cette partie du processus, car cela ne fonctionne que lorsque les exigences absolues sont relativement peu nombreuses; sinon vous vous retrouvez avec un problème incroyablement énorme !

Dans l'étape suivante, nous créons une série de tableaux et affectons au hasard des participants aux tableaux pour une configuration initiale, et un score est calculé pour représenter le nombre d'exigences floues qui ont été satisfaites. Les paires de convives sont commutées au hasard et le score est recalculé pour ces tables afin de déterminer si la nouvelle configuration est préférable.

Cette partie du processus devrait idéalement être répétée avec plusieurs configurations initiales, et peut facilement être calculée en parallèle.

Je pense que tout arrangement de sièges valide équivaut à un hypergraphe d-régulier sur | S | sommets, où d est le nombre de dîners, avec un classement au plus k et un codegree maximum 1. La solution triviale est d'avoir tout le monde toujours assis seul, mais je suppose que le but est de minimiser le nombre de tables?