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

23

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 = 5Sk|S||S|=45k=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.kSk

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.Sk

Christian Lindig
quelle
IIRC, das klingt nach dem Hamilton-Waterloo-Problem.
Juho
Ein Blick auf ein Papier über das Hamilton-Waterloo-Problem vermittelt den Eindruck, dass es sich um das strengere Problem handelt, sicherzustellen, dass ein Teilnehmer genau einmal nebeneinander sitzt.
Christian Lindig
1
Kirkmans Schulmädchenproblem scheint von ähnlicher Natur zu sein und könnte ein Ausgangspunkt sein.
Christian Lindig

Antworten:

11

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)|xF}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,,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)|xF}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.k2k

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.FkF×F

Insbesondere Mahlzeit hat k Tabellen { ( x , a x + b ) | x F } für jedes b F .ak{(x,ax+b)|xF}bF

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.2k2k22k2k=45{(x,x)|xF}k1

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.

Manu
quelle
Dies ist eine interessante Konstruktion, aber aufgrund von für meinen speziellen Fall zu einschränkend S | = k 2 könnte aber als Untergrenze dienen. |S|=k2
Christian Lindig
Ich habe die Frage bearbeitet, um allgemeinere Parameter zu behandeln.
Manu
1
Ich glaube, dass [block design] ( en.wikipedia.org/wiki/Block_design ) der geeignete Rahmen für den allgemeinen Fall ist, wie von domotorp unten ausgeführt. Ich mag jedoch den konstruktiven Aspekt und akzeptiere dies als eine gute Antwort.
Christian Lindig
3
Ich bin gespannt, ob es eine Lösung mit 10 Mahlzeiten gibt; Ich habe ein bisschen gegoogelt, aber keine Antwort gefunden. Wie sieht es aus, wenn die beste Lösung gefunden wurde, damit die Organisatoren die Namen der Teilnehmer einfügen und alle Sitzplatzzuweisungen zurückerhalten können? Wäre das für sie nützlich? Wenn wir dies vereinfachen, können andere Workshops diese schöne Tradition von Dagstuhl übernehmen.
Manu
1
Nettes Update. Wir sollten zu Ihren Ehren ein Bier bei Dagstuhl trinken, wenn dies umgesetzt wird :)
Suresh Venkat
4

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|=nnkn/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 ) .Sn/kkΘ(nk)

nΘ(n2)O(n/k)

n1k1

Vinayak Pathak
quelle
3

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.)

domotorp
quelle
Ich möchte, dass sich zwei Leute höchstens einmal treffen. Die Identität der Tabelle ist kein Problem, und ich bin mir nicht sicher, wie wichtig es ist, als Teil Ihrer Antwort am selben Tisch zu sitzen , aber ich werde die verknüpfte Definition nachschlagen.
Christian Lindig
2

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.

Chimärencoder
quelle
|S|
0

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?

Travis
quelle
1
Die Anzahl der Tabellen ist in dieser Einstellung festgelegt. Und es ist streng genommen weniger als die Anzahl der Leute.
Suresh Venkat