Gute Sitzordnung für die Reihenfolge der Mahlzeiten und Tische der Größe k für eine Gruppe von Personen

Bei einer bestimmten von Personen möchte ich sie zu einer Abfolge von Mahlzeiten an Tischen der Größe . (Natürlich gibt es genug Tische, an denen alle zu jeder Mahlzeit Platz haben.) Ich möchte dies so arrangieren, dass niemand zweimal mit derselben Person einen Tisch teilt. Typische Werte sind und und 6 bis 10 Mahlzeiten.k | S | | S | = 45 k = $S$$k$$|S|$$|S|=45$$k=5$

Abstrakter ausgedrückt möchte ich eine Folge von Partitionen von so dass jede Partition aus paarweise disjunkten Untergruppen der Kardinalität und der hinzugefügten globalen Eigenschaft besteht, dass jede Schnittmenge zwischen zwei solchen Untergruppen nicht mehr als ein Element enthält. Ich vermute, dass dies als graphentheoretisches oder kombinatorisches Problem formuliert werden kann.$S$$k$

Ich wäre dankbar für eine bessere Formulierung des Problems und Hinweise auf relevante Literatur, da diese außerhalb meines Bereichs liegt.

Hintergrund: Hier könnten Sitzordnungen auf Schloss Dagstuhl eingerichtet werden, bei denen viele Informatiker im Laufe einer Woche über ihre Forschungsergebnisse diskutieren. Derzeit wird zufällig und nicht überraschend gesetzt. Einige Leute sitzen im Laufe einer Woche zweimal (oder öfter) mit denselben Leuten zusammen. Es überrascht auch nicht, dass wir darüber einige Beschwerden und vage Vorschläge zur Verbesserung erhalten. Ich würde das gerne besser verstehen. Eine stärkere Formulierung des Problems beinhaltet die Optimierung, wer nebeneinander sitzt, aber ich glaube, dass dies für Tabellen der Größe 5 nicht relevant ist.

Außerhalb der Anwendung ist meines Erachtens die Frage interessant , wie viele Mahlzeiten für ein bestimmtes und k maximal serviert werden können , dh wie viele solche Partitionen existieren.$S$$k$

Hier ist eine Variante der ursprünglichen Antwort (unten), die die gewünschte Einstellung bietet: Tabellen der Größe 5, 45 Personen und 10 Mahlzeiten, mit der Ausnahme, dass eine Mahlzeit einige Tabellen der Größe 4 enthält.

Sei das Feld der Größe 9. Wähle 4 vertikale, entartete Linien { ( b , x ) | x ∈ F } für jedes b = 0 , 1 , 2 , 3 und erkläre ihr Volk für "leer". Wir haben 81 - 9x4 = 45 Leute.$F$$\{(b,x) | x \in F\}$$b = 0,1,2,3$

9 Mahlzeiten werden durch Pisten . Die Schnittpunkte mit den 4 leeren degenerierten Linien reduzieren die Tabellengröße auf 9-4 = 5.$a = 0,1,\ldots,8$

Eine zusätzliche Mahlzeit ergibt sich aus den verbleibenden entarteten Linien für jedes b = 4 , 5 , 6 , 7 , 8 . Hier ist die Tischgröße 9. Wir können jedoch (in jeder Lösung) einen Tisch der Größe 9 in einen Tisch der Größe 5 und einen Tisch der Größe 4 aufteilen.$\{(b,x) | x \in F\}$$b = 4,5,6,7,8$

Wenn es ein paar mehr Leute gibt, kann man das Feld der Größe 11 benutzen.

Lassen Sie uns zuerst Personen und k Mahlzeiten behandeln.$k^2$$k$

Wählen Sie eine endliche Feld der Größe k und identifizieren Menschen mit F × F . Zu jeder Mahlzeit gibt es eine Neigung, zu einer Tabelle eine Linie parallel zu dieser Neigung.$F$$k$$F \times F$

Insbesondere Mahlzeit hat k Tabellen { ( x , a x + b ) | x ∈ F } für jedes b ∈ F .$a$$k$$\{(x,ax+b) | x \in F\}$$b \in F$

Die gewünschte Kreuzungseigenschaft ist die Tatsache, dass sich Linien mit unterschiedlichen Steigungen in genau einem Punkt schneiden.

Um mit Personen umzugehen, teilen Sie sie in zwei Gruppen von jeweils k 2 auf und wenden Sie die obige Konstruktion auf jede Gruppe an. Um 2 k 2 - k = 45 zu behandeln , beschriften Sie (in der ersten Gruppe) eine feste Linie wie { ( x , x ) | x ∈ F } als "leer". Sie können ein paar Tische mit k - 1 Personen haben.$2k^2$$k^2$$2k^2 - k = 45$$\{(x,x)|x\in F\}$$k-1$

Für mehr Mahlzeiten könnte man zB zu Beginn der 6. Mahlzeit eine andere Aufteilung in zwei Gruppen wählen. (Angenommen, Sie verschachteln die ursprüngliche Partition, um sicherzustellen, dass die beiden Gruppen "gemischt" werden.) Natürlich kann dies jedoch zu einigen Überschneidungen führen.

Hier ist eine (lose?) Obergrenze für die Anzahl der Mahlzeiten, die Sie servieren können.

Lassen und n sei teilbar durch k . Angenommen, Sie haben genau n / k Tische und möchten, dass jeder Tisch während jeder Mahlzeit voll ist.$|S| = n$$n$$k$$n/k$

Erstellen Sie für jede Mahlzeit ein Diagramm mit einem Knoten für jede Person in und einer Kante, wenn sich zwei Personen einen Tisch teilen. Diese Grafik ist eine Sammlung von n / k Cliquen der Größe k . Die Anzahl der Kanten im Graphen beträgt also Θ ( n k ) .$S$$n/k$$k$$\Theta(nk)$

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

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

Wenn Sie möchten, dass zwei Personen genau einmal am selben Tisch sitzen, wird dies als auflösbares 2-Design bezeichnet und wurde vielfach untersucht. Wenn Sie ein paar Mahlzeiten auslassen, ist das natürlich eine Lösung für Ihr Problem, wenn sich zwei Personen höchstens einmal treffen können. (Möglicherweise gibt es aber auch andere Lösungen.)

Ich bin nicht sicher, ob Sie einen deterministischen Algorithmus benötigen, aber ich habe in der Vergangenheit ein ähnliches Problem mit einer Markov-Ketten-Monte-Carlo-Methode gelöst .

Sie können ein funktionierendes Beispiel für diesen Ansatz auf Github sehen - dieses Programm versucht, eine Gruppe von Personen an Tischen fester Größe unter Berücksichtigung einer Reihe von Sitzbeschränkungen zu platzieren, die entweder positiv oder negativ sein können ("muss" oder "darf nicht"). ) und entweder absolut oder relativ ("bevorzugt").

Hinweis: Dieses Programm löst nicht genau dasselbe Problem, das Sie vorschlagen, aber es demonstriert eine funktionierende Markov-Ketten-Monte-Carlo-Methode, und es ist nah genug, dass Sie es leicht nach Bedarf für Ihr Problem anpassen können.

Das Programm löst das Problem für ein Abendessen. In Ihrem Fall besteht eine einfache Möglichkeit, sich dem Problem zu nähern, darin, den Algorithmus für jedes Abendessen einmal auszuführen und die vorherigen Begleiter jedes Abendessens als unscharfe oder absolut negative Anforderungen bereitzustellen. (Der Vorteil von Fuzzy-Anforderungen ist, dass Sie garantiert sind, dass der Algorithmus bei allen Eingaben anhält, auch wenn keine perfekte Anordnung gefunden werden kann.)

In diesem Prozess würden wir zuerst versuchen, jedes Abendessen gemäß den absoluten Anforderungen zu platzieren. Sie können diesen Teil des Prozesses überspringen, da er nur funktioniert, wenn die absoluten Anforderungen relativ gering sind. ansonsten hast du ein unglaublich großes Problem !

Im nächsten Schritt erstellen wir eine Reihe von Tabellen und weisen den Tabellen nach dem Zufallsprinzip Teilnehmer für eine Erstkonfiguration zu. Anschließend wird eine Punktzahl berechnet, die die Anzahl der erfüllten Fuzzy-Anforderungen darstellt. Diners-Paare werden zufällig gewechselt, und die Punktzahl wird für diese Tabellen neu berechnet, um zu bestimmen, ob die neue Konfiguration vorzuziehen ist.

Dieser Teil des Prozesses sollte idealerweise mit mehreren Anfangskonfigurationen wiederholt werden und kann leicht parallel berechnet werden.

Ich denke, jede gültige Sitzordnung entspricht einem d-regulären Hypergraphen auf | S | Eckpunkte, wobei d die Anzahl der Abendessen ist, mit Rang höchstens k und maximalem Grad 1. Die triviale Lösung besteht darin, dass jeder für sich sitzt, aber ich denke, das Ziel ist es, die Anzahl der Tische zu minimieren?