给定一个具有n个元素的C(允许重复)，并且将P划分为n
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具有十二个以上的元素时，它的效率很低。
提前致谢
菲利普
最佳答案
分解顺序与您无关紧要的事实使它变得更加困难。也就是说，您正在查看{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处崩溃。我不知道它会在哪里崩溃。但是鉴于您要遍历一组分区，因此在某个很小的点上它将分解。)