algorithm - 计算具有给定大小的集合的子集

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 的一堆，发现我们可以将其划分如下，按字典顺序重新排列每个剩余的分区策略:

[4]离开 [[1, 1, 1], [2, 2, 1], [1, 4, 1]] = [[2, 2, 1], [1, 4, 1], [1, 1, 1]] .

[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, 0, 1]离开 [[2, 1, 1], [2, 2, 1], [0, 1, 1], [1, 3, 1]] = [[2, 2, 1], [2, 1, 1], [1, 3, 1]]

[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]]

[2, [1, 1], 0]离开 [[3, 1, 1], [1, 2, 1], [1, 4, 1]] = [[3, 1, 1], [1, 4, 1], [1, 2, 1]]

[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]]

[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

[1, [2, 1]]离开 [[4, 1, 1], [0, 1, 1], [1, 1, 1], [1, 4, 1]] = [[4, 1, 1], [1, 4, 1], [1, 1, 1]]

[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]]

[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]]

[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]]

[0, [2, 2]]离开 [[5, 1, 1], [0, 2, 1], [1, 4, 1]] = [[5, 1, 1], [1, 4, 1]]

[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]]

[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]]

[0, [1, 1], [1, 1]]离开 [[5, 1, 1], [1, 2, 1], [0, 2, 1], [1, 2, 1]] = [[5, 1, 1,], [1, 2, 2]]

[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]]

[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 时崩溃。我不知道它会在哪里崩溃。但鉴于您正在迭代一组分区，在某个相当小的点上它会分解。)