Хорошая расстановка сидений для последовательности блюд и столов размера k для группы людей

Учитывая набор людей, я хотел бы сидеть их для последовательности блюд за столами размера . (Конечно, для каждого приема пищи достаточно столов, чтобы все .) Я бы хотел организовать это так, чтобы никто не делил стол с одним и тем же человеком дважды. Типичными значениями являются и и от 6 до 10 приемов пищи.k | S | | S | = 45 к = $S$$k$$|S|$$|S|=45$$k=5$

Говоря более абстрактно, я хотел бы найти последовательность разделов такую, что каждый раздел состоит из попарно непересекающихся подмножеств мощности и дополнительного глобального свойства, заключающегося в том, что любое пересечение между двумя такими подмножествами содержит не более одного элемента. Я подозреваю, что это можно сформулировать как теоретическую или комбинаторную задачу о графе.$S$$k$

Я был бы признателен за лучшую формулировку проблемы и ссылки на соответствующую литературу, поскольку она находится за пределами моей области.

Справочная информация: это может быть использовано для организации рассадки в Schloss Dagstuhl, куда многие компьютерные специалисты приезжают, чтобы обсудить свои исследования в течение недели. В настоящее время рассадка производится случайным образом, и неудивительно, что некоторые люди сидят с одними и теми же людьми дважды (или чаще) в течение недели. Также неудивительно, что мы получаем некоторые жалобы по этому поводу и расплывчатые предложения, как улучшить это. Я хотел бы понять это лучше. Более сильная формулировка проблемы включает в себя оптимизацию того, кто сидит рядом, но я считаю, что это не относится к таблицам размера 5.

Вне заявки я думаю, что интересным является вопрос о максимальном количестве приемов пищи, которое может быть подано для заданных и , т. Е. Сколько таких перегородок существует.$S$$k$

Вот вариант исходного ответа (ниже), который задает желаемую настройку: таблицы размером 5, 45 человек и 10 приемов пищи, за исключением того, что один прием пищи имеет несколько таблиц размера 4.

Пусть поле размера 9. Выберите 4 вертикальные вырожденные линии для каждого и объявить своих людей "пустыми". Нам осталось 81 - 9х4 = 45 человек.{ ( b , x ) | x ∈ F } b = 0 , 1 , 2 , $F$$\{(b,x) | x \in F\}$$b = 0,1,2,3$

9 блюд даны по уклонам . Пересечения с 4 пустыми вырожденными линиями уменьшают размер таблицы до 9-4 = 5.$a = 0,1,\ldots,8$

Дополнительное питание дается оставшимися вырожденными линиями для каждого . Здесь размер таблицы равен 9. Однако (в любом решении) мы можем разбить таблицу размера 9 на таблицу размера 5 и одну на размер 4.b = 4 , 5 , 6 , 7 , $\{(b,x) | x \in F\}$$b = 4,5,6,7,8$

Если есть еще несколько человек, можно использовать поле размера 11.

Сначала давайте разберёмся с людьми и приемами пищи.$k^2$$k$

Выберите конечное поле от размера и идентифицировать людей с . Каждой трапезе соответствует уклон, а таблице - линия, параллельная этому уклону.k F × $F$$k$$F \times F$

В частности, еда имеет таблиц для каждого .k { ( x , a x + b ) | х ∈ F } б ∈ $a$$k$$\{(x,ax+b) | x \in F\}$$b \in F$

Желаемое свойство пересечения - это тот факт, что линии с разными наклонами пересекаются ровно в одной точке.

Чтобы справиться с людьми, разделите их на две группы по каждой и примените приведенную выше конструкцию к каждой группе. Чтобы обработать , пометьте (в первой группе) фиксированную строку, например как "пустую". У вас может быть несколько столов с людьми.k 2 2 k 2 - k = 45 { ( x , x ) | x ∈ F } k - $2k^2$$k^2$$2k^2 - k = 45$$\{(x,x)|x\in F\}$$k-1$

Для большего количества приемов пищи можно, например, выбрать другой раздел в двух группах в начале 6-го приема пищи. (Допустим, вы чередуете исходный раздел, чтобы две группы «смешались».) Хотя, конечно, это может привести к некоторым пересечениям.

Вот (свободная?) Верхняя граница количества блюд, которые вы можете подавать.

Пусть и предположим, что делится на . Также предположим, что у вас есть ровно столов, и вы хотите, чтобы каждый стол был заполнен во время каждого приема пищи.n k n /$|S| = n$$n$$k$$n/k$

Для каждого приема пищи постройте график с узлом для каждого человека в и ребром, когда два человека делят таблицу. Этот граф представляет собой набор из клик каждого размера . Таким образом, число ребер в графе равно .n / k k Θ ( n k $S$$n/k$$k$$\Theta(nk)$

Поскольку вы не хотите, чтобы какое-либо ребро встречалось в двух разных приемах пищи, и поскольку общее число ребер, возможных на наборе вершин размера равно , это показывает, что вы можете подавать только питание.Θ ( n 2 ) O ( n / k $n$$\Theta(n^2)$$O(n/k)$

На самом деле, здесь нетрудно найти константы, и когда вы выполняете математику, вы получаете верхнюю границу ровно , которая для ваших типичных значений равна 11.$\frac{n-1}{k-1}$

Если вы хотите, чтобы какие-то два человека сидели за одним столом ровно один раз, то это называется разрешимым 2-дизайном и много изучено. Конечно, если пропустить несколько приемов пищи, это поможет решить вашу проблему, когда два человека могут встретиться не более одного раза. (Но другие решения могут существовать, я полагаю.)

Я не уверен, что вам нужен детерминированный алгоритм, но я уже решал аналогичную проблему в прошлом, используя метод Монте-Карло с цепью Маркова .

Вы можете увидеть рабочий пример этого подхода на Github - эта программа пытается разместить группу людей за столами фиксированного размера, учитывая набор ограничений на размещение, которые могут быть как положительными, так и отрицательными («должен» или «не должен»). ) и либо абсолютный, либо относительный («предпочтительный»).

Примечание: эта программа не решает точно ту же проблему, которую вы предлагаете, но она дает рабочую демонстрацию метода Монте-Карло с цепью Маркова, и она достаточно близка, чтобы вы могли легко настроить ее по мере необходимости для вашей задачи.

Программа решает проблему за один ужин, но в вашем случае простым способом решения этой проблемы было бы запускать алгоритм один раз для каждого ужина, каждый раз предоставляя предыдущим компаньонам каждого посетителя либо нечеткие, либо абсолютные отрицательные требования. (Преимущество нечетких требований состоит в том, что вы гарантируете, что алгоритм остановится на всех входах, даже если идеальное расположение не может быть найдено).

В этом процессе мы сначала попытаемся разместить каждого посетителя в соответствии с абсолютными требованиями - вы можете пропустить эту часть процесса, поскольку он работает только тогда, когда абсолютные требования относительно малы; в противном случае вы столкнетесь с невероятно огромной проблемой !

На следующем шаге мы создаем серию таблиц и случайным образом назначаем участников таблицам для начальной конфигурации, и вычисляется оценка для представления числа нечетких требований, которые были удовлетворены. Пары посетителей выбираются случайным образом, и оценка этих таблиц пересчитывается для определения предпочтительности новой конфигурации.

Эта часть процесса в идеале должна повторяться с несколькими начальными конфигурациями и может быть легко вычислена параллельно.

Я думаю, что любое действительное расположение мест эквивалентно d-регулярному гиперграфу на | S | вершины, где d - количество обедов с рангом не более k и максимальной кодовой степенью 1. Тривиальное решение состоит в том, чтобы каждый всегда сидел один, но я полагаю, что цель состоит в том, чтобы минимизировать количество столов?