Найти все возможные разбиения n элементов с подмножествами размера k, где два элемента совместно используют один и тот же набор только один раз

Question

У меня есть n элементов, которые нужно разбить на x наборов, каждый набор должен содержать ровно k = 4 элемента.

Мне нужно найти все возможные разделы с ограничением, которое каждая пара элементов разделяет толькоодин и тот же набор один раз.

Так что, если я начну с [1 2 3 4] [5 6 7 8] [...], все последовательные разделы не могут удерживаться, например, [1 2 XX] или [XX 1 3].множества неупорядочены.

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

Пример: У меня 32 мыши, которых можно поместить в 8 клеток, по 4 на клетку.Мышей следует вращать между клетками так, чтобы они никогда не встречались с другой мышью дважды.Как часто вы можете это сделать и каковы конфигурации?

Answer 1

Это пример «проблемы социального игрока в гольф». У Уорика Харви была страница (http://www.cs.st -andrews.ac.uk / ~ wh / golf / ) с кучей решений для разных размеров задач, но, похоже, она не работает Ответ в вашем случае оказывается 10 вращений, но я не знаю, каковы фактические конфигурации. Вот решение с 9 вращениями: http://www.cs.st -andrews.ac.uk / ~ ianm / CSPLib // prob / prob010 / solution

Это нерешенная проблема для общих n и k.

Answer 2

Ваша формулировка проблемы («все возможные разделы») вводит в заблуждение.

Давайте исправим условия (если вы согласны): раздел (p) является конкретным (изавершено) распределение n элементов в x блоков , каждый из которых содержит k = 4 элемента .(Я использую термин «блок» вместо «набор», чтобы избежать путаницы) (Кстати, обратите внимание, что, если мы примем это определение, то вам придется повторить свою фразу о «последовательных разделах», это не имеет смысла).

Тогда, давайте назовем P ={p1,p2 ...} набор всех возможных разделов.Теперь нас интересуют некоторые подмножества P (мы можем назвать каждое из них «правильным набором разбиений»).PSOF - это набор разделов с заданным свойством: нет двух разделов, которые отображают одну и ту же пару элементов в один и тот же блок.(Мы также можем добавить свойство максимальности: невозможно добавить другой раздел без нарушения правила).

Теперь непонятно, хотите ли вы:

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

Ни один из них не кажется мне легким.(Извините, я знаю, что это не ответ, а пояснение, но оно не уместилось в комментариях)