Phi*_*peC 10 algorithm math combinatorics
给定具有n个元素的集合C(允许重复)和n
P = {i1,i2,.../i1 + i2 + ... = n} 的分区P 在大小为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有十几个元素时效率很低.
在此先感谢
Philippe
事实上，分解的顺序对你来说并不重要，这使得分解变得更加困难。也就是说，您正在查看的内容{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]]现在每个子问题都可以递归地解决。这可能感觉我们正在构建所有它们，但事实并非如此，因为我们记住了递归步骤。事实证明，有很多方法可以让前两组 8 人最终得到相同的 5 人。通过记忆，我们不需要重复地重新计算这些解决方案。
也就是说，我们会做得更好。12 个元素组成的组应该不会造成问题。但我们并没有做得更好。如果它开始在 30 个左右的元素组（具有有趣的分区集）附近崩溃，我不会感到惊讶。（我还没有编码。它可能在 30 时很好，在 50 时崩溃。我不知道它会在哪里崩溃。但考虑到您正在迭代分区集，在某个相当小的点上它会分解。）