algorithm - 具有不同组容量的组组合

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 个元素的子集。这被称为 multinomial *，并计算如下:

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

基本上，您要做的是:

1) 为 A 组选择 3 个元素:n1 = 9 选择 3。
2) 为 B 组选择 2 个元素:n2 = 6 选择 2。
3) 其余4个元素为C组。

总计:

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

*) 请参阅“分区”部分

编辑: 我在对该问题的评论中注意到一些关于特殊要求的内容(例如，6 讨厌 9)。如果您有这样的人，请先处理它们(将 9 个放在一组中，将 6 个放在另外两组中的一组中)，然后再处理剩余的。