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

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

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

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

Близки к этой проблеме числа Стирлинга второго рода. Однако они решают проблему только для наборов произвольного размера.

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


partitioning permutation combinatorics
person ypnos    schedule 18.06.2010    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Это пример «социальной проблемы игрока в гольф». У Уорвика Харви была страница (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.

person Joe Neeman    schedule 13.09.2010
comment
Большое спасибо. Я нашел этот ресурс: cs.brown.edu/~sello/golf.html, который ссылается на зеркало страницы Харви: csplib.org/prob/prob010/ index.html и многие другие. - person ypnos; 14.09.2010

arrow_upward
1
arrow_downward

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

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

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

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

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

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

person leonbloy    schedule 04.07.2010
comment
Большое спасибо за разъяснения. Он очень четко резюмирует постановку проблемы. Я хочу найти самый большой максимальный PSOF (как вы сказали, возможно, все они имеют одинаковый размер). - person ypnos; 05.07.2010
comment
Еще одно уточнение: порядок ящиков имеет значение или нет? Я предполагаю, что это не так. т. е., если два раздела отличаются только тем, что коробки 1 и коробки 2 заменены местами, они считаются одинаковыми. Верно? - person leonbloy; 05.07.2010