Групповые комбинации с различными групповыми возможностями

Question

Ну, у меня вопрос о том, какой алгоритм будет наиболее подходящим для моей проблемы. Допустим, у меня есть 3 группы:

Group A) 1 2 3 
Group B) 5 4
Group C) 9 6 7 8

Теперь я хотел бы получить все возможные группы с этими членами (1-8) и группы с вместимостью 3, 2, 4.

Примечание:

Group A) 3 1 2
Group B) 5 4
Group C) 7 8 9 6

считается той же групповой комбинацией, что и вышеуказанная комбинация.

Я пробовал все возможные комбинации этих чисел (1-8), но зная, что у меня может быть группа из 30 членов, я бы придумал 265252859812191058636308480000000 различных комбинаций, но это слишком много.

Я пытался искать неизоморфные группы, но безуспешно.

Answer 1

Я предполагаю, что никакие числа не могут быть введены дважды (у вас есть два 3 в вашем первом примере и два 5 в вашем втором ...), поэтому я просто буду использовать цифры 1-9 и одинаковое количество элементов в каждой группе.

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

Ваша проблема довольно стандартная - вы хотите разделить набор из 9 элементов на подмножества из 3, 2 и 4 элементов соответственно. Это известно как полином *, и рассчитывается следующим образом:

n = 9! / (3!*2!*4!)

По сути, то, что вы делаете, это:

1) выберите 3 элемента для группы A: n1 = 9 choose 3.
2) выберите 2 элемента для группы B: n2 = 6 choose 2.
3) остальные четыре элемента относятся к группе С.

Всего:

n = n1 * n2 = 9!/(3!6!) * 6!/(2!4!) = 9! / (3!*2!*4!)

*) См. Раздел "Перегородки"

РЕДАКТИРОВАТЬ: Я заметил кое-что о специальных требованиях (6 ненависти 9, например) в комментарии к вопросу. Если у вас есть такие, сначала посмотрите на них (поместите 9 в одну группу, 6 в одну из двух других), а затем посмотрите на остатки.