计算具有给定尺寸的集合的子集

Question

给定具有n个元素（允许重复）的集合C和n的分区P
P = {i1，i2，...，i1 + i2 + ... = n} 对于大小为i1，i2，...的子集，C有多少种不同的分解？

实施例：

C = {2 2 2 3} 

P = {2 2} 
C = {2 2} U {2 3} 

P = {1 1 2} 
C = {2} U {2} U {2 3} 
C = {2} U {3} U {2 2} 

P = {1 3} 
C = {2} U {2 2 3} 
C = {3} U {2 2 2} 

我有一个解决方案，但它是低效当C具有比元素的十几。
在此先感谢
菲利普

Answer 1

是分解的顺序并不重要，你使得它更难的事实。也就是说，您正在查看{2 2} U {2 3}与{2 3} U {2 2}相同。尽管如此，我还是有一个比你有更好的算法，但不是很好。

让我从一个现实复杂的例子开始。我们的设置将是A B C D E F F F F G G G G。分区将是1 1 1 1 2 2 5。

我的第一个简化将是用数据结构[[2, 4], [5, 1]]来表示我们关心的信息，即2个元素重复4次，5个重复一次。

我的第二个明显的复杂情况是用[[5, 1, 1], [2, 2, 1], [4, 1, 1]来表示分区。该模式可能并不明显。每个条目的形式是[size, count, frequency]。因此，大小为2的2个分区的一个不同实例变为[2, 2, 1]。我们还没有使用频率，但它正在计数相同大小和共同性的可区分的堆。

现在我们要递归如下。我们将采用最常见的元素，并找出所有使用它的方法。所以在我们的例子中，我们采取大小4成堆的一个，并且发现我们可以把它如下，按照字典顺序重新排列其余的每个分区策略：

1. [4]离开[[1, 1, 1], [2, 2, 1], [1, 4, 1]] = [[2, 2, 1], [1, 4, 1], [1, 1, 1]]。
2. [3, [1, 0], 0]离开[[2, 1, 1], [1, 1, 1], [2, 1, 1], [1, 4, 1]] = [[2, 1, 2], [1, 4, 1], [1, 1, 1]。 （请注意，我们现在使用频率。）
3. [3, 0, 1]离去[[2, 1, 1], [2, 2, 1], [0, 1, 1], [1, 3, 1]] = [[2, 2, 1], [2, 1, 1], [1, 3, 1]]
4. [2, [2, 0], 0]离去[[3, 1, 1], [0, 1, 1], [2, 1, 1], [1, 4, 1]] = [[3, 1, 1], [2, 1, 1], [1, 4, 1]]
5. [2, [1, 1], 0]离去[[3, 1, 1], [1, 2, 1], [1, 4, 1]] = [[3, 1, 1], [1, 4, 1], [1, 2, 1]]
6. [2, [1, 0], [1]]离去[[3, 1, 1], [1, 1, 1], [2, 1, 1], [0, 1, 1], [1, 3, 1]] = [[3, 1, 1], [2, 1, 1], [1, 4, 1], [1, 1, 1]]
7. [2, 0, [1, 1]]离去`[[3，1,1]，[2,2，1]，[0 ，1,2,1]，[1,2,1]] = [[3,1,1]，[2,2,1]，[1,2,1]] 1
8. [1, [2, 1]]离开[[4, 1, 1], [0, 1, 1], [1, 1, 1], [1, 4, 1]] = [[4, 1, 1], [1, 4, 1], [1, 1, 1]]
9. [1, [2, 0], [1]]离开[[4, 1, 1], [0, 1, 1], [2, 1, 1], [0, 1, 1], [1, 3, 1]] = [[4, 1, 1], [2, 1, 1], [1, 3, 1]]
10. [1, [1, 0], [1, 1]]离开[[4, 1, 1], [1, 1, 1], [2, 1, 1], [0, 2, 1], [1, 2, 1]] = [[4, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 1]]
11. [1, 0, [1, 1, 1]]离开[[4, 1, 1], [2, 2, 1], [0, 3, 1], [1, 1, 1]] = [[4, 1, 1], [2, 2, 1], [1, 1, 1]]
12. [0, [2, 2]]离开[[5, 1, 1], [0, 2, 1], [1, 4, 1]] = [[5, 1, 1], [1, 4, 1]]
13. [0, [2, 1], [1]]离开[[5, 1, 1], [0, 1, 1], [1, 1, 1], [0, 1, 1], [1, 3, 1]] = [[5, 1, 1], [1, 3, 1], [1, 1, 1]]
14. [0, [2, 0], [1, 1]]离开[[5, 1, 1], [0, 2, 1], [2, 1, 1], [0, 2, 1], [1, 2, 1]] = [[5, 1, 1], [2, 1, 1], [1, 2, 1]]
15. [0, [1, 1], [1, 1]]离开[[5, 1, 1], [1, 2, 1], [0, 2, 1], [1, 2, 1]] = [[5, 1, 1,], [1, 2, 2]]
16. [0, [1, 0], [1, 1, 1]]离开[[5, 1, 1], [1, 1, 1], [2, 1, 1], [0, 3, 1], [1, 1, 1]] = [[5, 1, 1], [2, 1, 1], [1, 1, 2]]
17. [0, 0, [1, 1, 1, 1]]离开[[5, 1, 1], [2, 2, 1], [0, 4, 1]] = [[5, 1, 1], [2, 2, 1]]

现在每个子问题的那些可以递归解决。这可能觉得我们正在构建它们的所有方式，但我们不是，因为我们memoize的递归步骤。事实证明，前面两组8人可以用相同的5个剩余部分结束。通过记录我们不需要重复计算这些解决方案。

这就是说，我们会做得更好。 12个元素组不应该成为问题。但我们没有做那好多了。如果它开始打破围绕30个左右分组的有趣的分区组的某个地方，我不会感到惊讶。 （我没有编码，在30点可能会好，在50点也可以，但我不知道它会在哪里崩溃，但是考虑到你正在迭代多组分区，在一些相当小的点上它会变成将分解。）

Answer 2

所有分区都可以在两个阶段找到。

第一个：从P开始对n，P_S={P_i1, P_i2, ..., P_ip}进行新的有序划分，将相同的i相加。

P = {1, 1, 1, 1, 2, 2, 5} 
P_S = (4, 4, 5) 

使分区C{C_i1, C_i2, ..., C_ip}相对于P_S。请注意，C_ix是多套的，如C。它按照最终分区的大小将C分区成多集。

二：对于每个{C_i1, C_i2, ..., C_ip}和每个ix, x={1,2,...,p}查找数的C_ix分区成t（在P数目的ix's）设置与ix元件。致电此号码N(C_ix,ix,t)。

分区总数为：

sum by all {C_i1, C_i2, ..., C_ip} (product N(C_ix,ix,t) ix={1,2,...,p}) 

第一部分可以完成递归很简单。其次更复杂。与k元件多设置M成n份的分区相同发现与来自M元素的所有部分排序列表。部分顺序列表的类型为：

a_1_1, a_1_2, ..., a_1_k, a_2_1, a_2_2, ..., a_2_k, .... 

凡a_i_x <= a_i_y如果x < y和(a_x_1, a_x_2, ..., a_x_k) lexicographic <= (a_y_1, a_y_2, ..., a_y_k)如果x < y。有了这两个条件，可以递归地创建N(C_ix,ix,t)的所有分区。

在某些情况下N(C_ix,ix,t)很容易计算。限定|C_ix|在不同元件的数量多设置C_ix。

if t = 1 than 1 
if |C_ix| = 1 than 1 
if |C_ix| = 2 than (let m=minimal number of occurrences of elements in C_ix) floor(m/2) + 1 
in general if |C_ix| = 2 than partition of m in numbers <= t.