Dobre rozmieszczenie miejsc dla sekwencji posiłków i stolików wielkości k dla grupy osób

Biorąc pod uwagę zestaw $S$ osób, chciałbym im usiąść na sekwencji posiłków przy stolikach wielkości . (Oczywiście, jest wystarczająca ilość stolików, aby usiąść przy każdym posiłku.) Chciałbym tak ustawić, aby nikt nie dzielił stołu z tą samą osobą dwa razy. Typowe wartości to i$k$$|S|$$|S|=45$$k=5$ i 6 do 10 posiłków.

Mówiąc bardziej abstrakcyjnie, chciałbym znaleźć sekwencję partycji tak aby każda partycja składała się z par rozłącznych podzbiorów liczności$S$$k$ oraz dodanej właściwości globalnej, że każde przecięcie dwóch takich podzbiorów zawiera nie więcej niż jeden element. Podejrzewam, że można to sformułować jako problem teoretyczny lub kombinatoryczny.

Byłbym wdzięczny za lepsze sformułowanie problemu i wskazanie odpowiedniej literatury, ponieważ jest ona poza moją domeną.

Tło: może to być wykorzystane do aranżacji miejsc w Schloss Dagstuhl, gdzie wielu informatyków przyjeżdża, aby omówić swoje badania w ciągu tygodnia. Obecnie siedzenia są wykonywane losowo i nic dziwnego, że niektórzy ludzie siedzą z tymi samymi ludźmi dwa razy (lub częściej) w ciągu tygodnia. Nic dziwnego, że otrzymujemy skargi na ten temat i niejasne sugestie, jak to poprawić. Chciałbym to lepiej zrozumieć. Silniejsze sformułowanie problemu polega na optymalizacji, kto siedzi obok siebie, ale uważam, że nie dotyczy to tabel o rozmiarze 5.

Poza aplikacją myślę, że interesujące pytanie dotyczy maksymalnej liczby posiłków, które można podać dla danego i , tj. Ile takich partycji istnieje.$S$$k$

Oto wariant oryginalnej odpowiedzi (poniżej), który daje pożądane ustawienie: tabele wielkości 5, 45 osób i 10 posiłków, z tym wyjątkiem, że jeden posiłek ma kilka tabel wielkości 4.

Niech będzie polem wielkości 9. Wybierz 4 pionowe, zdegenerowane linie { ( b , x ) | x ∈ F } dla każdego b = 0 , 1 , 2 , $F$$\{(b,x) | x \in F\}$$b = 0,1,2,3$ i deklarują, że ich ludzie są „pustych”. Pozostaje nam 81 - 9x4 = 45 osób.

9 posiłków jest podawanych na stokach . Przecięcia z 4 pustymi zdegenerowanymi liniami zmniejszają rozmiar stołu do 9-4 = 5.$a = 0,1,\ldots,8$

Dodatkowy posiłek podaje pozostałe zdegenerowane linie dla każdego b = 4 , 5 , 6 , 7 , 8 . Tutaj rozmiar tabeli wynosi 9. Jednak (w dowolnym rozwiązaniu) możemy rozbić tabelę o rozmiarze 9 na tabelę o rozmiarze 5 i jedną o rozmiarze 4.$\{(b,x) | x \in F\}$$b = 4,5,6,7,8$

Jeśli jest jeszcze kilka osób, można użyć pola o rozmiarze 11.

Najpierw zajmiemy się osobami i $k^2$$k$ posiłkami.

Odbiór pola o skończonej o rozmiarze K i identyfikacji osób z F × F . Do każdego posiłku odpowiada nachylenie, a stole linia równoległa do tego nachylenia.$F$$k$$F \times F$

W szczególności posiłek ma k tabel { ( x , a x + b ) | x ∈ K } dla każdego b ∈ F .$a$$k$$\{(x,ax+b) | x \in F\}$$b \in F$

Właściwość przecięcia, którą chcesz, to fakt, że linie o różnych nachyleniach przecinają się dokładnie w jednym punkcie.

Aby obsłużyć osoby, podzielić je na dwie grupy k 2 każda, i zastosować konstrukcję powyżej do każdej grupy. Aby obsłużyć 2 k 2 - k = 45 , oznacz (w pierwszej grupie) linię stałą, taką jak { ( x , x ) | x ∈ F } jako „pusty”. Możesz mieć kilka stolików dla k - 1 osób.$2k^2$$k^2$$2k^2 - k = 45$$\{(x,x)|x\in F\}$$k-1$

Aby uzyskać więcej posiłków, można na przykład wybrać inny podział na dwie grupy na początku 6. posiłku. (Załóżmy, że przeplatasz oryginalną partycję, aby upewnić się, że obie grupy „mieszają się”.) Oczywiście może to spowodować pewne skrzyżowania.

Oto (luźna?) Górna granica liczby posiłków, które możesz podać.

Niech i załóżmy, że n jest podzielne przez k . Załóżmy również, że masz dokładnie n /$|S| = n$$n$$k$$n/k$ stołów i chcesz, aby każdy stół był pełny podczas każdego posiłku.

Dla każdego posiłku zbuduj wykres z węzłem dla każdej osoby w i krawędzią, gdy dwie osoby będą dzielić stół. Ten wykres jest zbiorem n / k klik dla każdej wielkości k . Zatem liczba krawędzi na wykresie wynosi Θ ( n k $S$$n/k$$k$$\Theta(nk)$ .

Ponieważ nie chcesz, aby krawędź występowała w dwóch różnych posiłkach, a ponieważ całkowita liczba krawędzi możliwych w zestawie wierzchołków o rozmiarze wynosi Θ ( n 2 ) , oznacza to, że możesz podawać tylko posiłki O ( n / k ) .$n$$\Theta(n^2)$$O(n/k)$

Właściwie nie jest trudno znaleźć tutaj stałe, a kiedy wykonujesz matematykę, dostajesz górną granicę dokładnie , co dla typowych wartości wynosi 11.$\frac{n-1}{k-1}$

Jeśli chcesz, aby jakieś dwie osoby siedziały dokładnie przy tym samym stole, to nazywa się to dwuwymiarową konstrukcją, która była przedmiotem wielu badań. Oczywiście pozwolenie na pominięcie kilku posiłków dałoby rozwiązanie problemu, gdy dwie osoby mogą spotkać się najwyżej. (Ale przypuszczam, że mogą istnieć inne rozwiązania).

Nie jestem pewien, czy potrzebujesz algorytmu deterministycznego, ale podobny problem rozwiązałem w przeszłości za pomocą metody Monte Carlo z łańcuchem Markowa .

Możesz zobaczyć działający przykład takiego podejścia na Githubie - ten program próbuje posadzić grupę ludzi przy stołach o ustalonym rozmiarze, biorąc pod uwagę zestaw ograniczeń siedzenia, które mogą być albo dodatnie, albo ujemne („musi” lub „nie może” ) oraz bezwzględny lub względny („preferowany”).

Uwaga: ten program nie rozwiązuje dokładnie tego samego problemu, który proponujesz, ale daje działającą demonstrację metody Monte Carlo z łańcuchem Markowa i jest wystarczająco blisko, aby można go było łatwo dostosować do potrzeb.

Program rozwiązuje problem jednej kolacji, ale w twoim przypadku łatwym sposobem rozwiązania problemu byłoby uruchomienie algorytmu raz na każdą kolację, za każdym razem podając poprzednich towarzyszy każdego z gości jako rozmyte lub absolutnie negatywne wymagania. (Zaletą rozmytych wymagań jest to, że masz gwarancję, że algorytm zatrzyma się na wszystkich danych wejściowych, nawet jeśli nie można znaleźć idealnego układu).

W tym procesie najpierw próbujemy ustawić każdą restaurację zgodnie z bezwzględnymi wymaganiami - możesz pominąć tę część procesu, ponieważ działa ona tylko wtedy, gdy bezwzględna liczba wymagań jest stosunkowo niewielka; w przeciwnym razie staniesz przed niewiarygodnie dużym problemem !

W następnym kroku tworzymy serię tabel i losowo przypisujemy uczestników do tabel w celu wstępnej konfiguracji, a wynik jest obliczany w celu odzwierciedlenia liczby spełnionych wymagań rozmytych. Pary dinerów są losowo przełączane, a wynik jest ponownie obliczany dla tych tabel, aby ustalić, czy nowa konfiguracja jest lepsza.

Ta część procesu powinna być idealnie powtórzona z kilkoma początkowymi konfiguracjami i może być łatwo obliczona równolegle.

Myślę, że każde prawidłowe ustawienie miejsc siedzących jest równoważne z hipergrrafem d-regular na | S | wierzchołki, gdzie d jest liczbą obiadów, z najwyżej rangą k i maksymalnym kodem 1. Trywialne rozwiązanie polega na tym, aby wszyscy zawsze siedzieli sami, ale myślę, że celem jest zminimalizowanie liczby stołów?