计算给定大小的集合的子集

Question

给定一个包含 n 个元素的集合 C（允许重复）和一个包含 n 的分区 P
P = {i1, i2, ... / i1+i2+... = n} C 在大小为 i1、i2、... 的子集中有多少种不同的分解？

示例：

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} 相同。我仍然有一个比你更好的算法，但不是很好。

让我从一个实际复杂的例子开始。我们的集合将是ABCDEFFFFGGG G。分区将为1 1 1 1 2 2 5。

我的第一个简化是用数据结构 [[2, 4], [5, 1]] 表示集合中我们关心的信息，这意味着 2 个元素重复 4 次，5 个元素重复重复一次。

我的第二个明显的复杂之处是用 [[5, 1, 1], [2, 2, 1], [4, 1, 1] 表示分区。模式可能并不明显。每个条目的格式为[大小、计数、频率]。因此，大小为 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, 2, 1 ], [1, 2, 1]] = [[3, 1, 1], [2, 2, 1], [1, 2, 1]]1 <
8. 代码>[1, [2, 1]]< /code> 留下 [[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]]

现在每个子问题都可以递归地解决。这可能感觉我们正在构建它们，但事实并非如此，因为我们记忆< /a> 递归步骤。事实证明，有很多方法可以让前两组 8 人最终得到相同的 5 人。通过记忆，我们不需要重复地重新计算这些解决方案。

也就是说，我们会做得更好。 12 个元素组成的组应该不会造成问题。但我们并没有做得更好。如果它开始在 30 个左右的元素组（具有有趣的分区集）附近崩溃，我不会感到惊讶。 （我还没有编码。它可能在 30 时很好，在 50 时崩溃。我不知道它会在哪里崩溃。但考虑到您正在迭代分区集，在某个相当小的点上它 < em>将会崩溃。）

Answer 2

所有分区都可以在 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)

相对于 P_S 对 C 进行划分 {C_i1, C_i2, ..., C_ip}。请注意，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} )

第一部分可以非常简单地递归完成。二是比较复杂。将多集 M 划分为具有 k 元素的 n 部分，与查找具有 MM.部分顺序列表的类型为：

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

其中 a_i_x <= a_i_y if x <= y 和 (a_x_1, a_x_2, ..., a_x_k) 字典 <= (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.