唯一子集生成的动态规划实现

您所称的“唯一子集生成”更好地称为 integer partitions with distinct parts .Mathworld有一个条目 the Q function ,它统计具有不同部分的分区数。

然而 也就是说,您的函数不计算普通分区(即。 n -> (n) )所以你要找的是 Q(n) - 1 ,它生成 sequence that you linked in your question --中的分区数 至少2 不同的部分。 This answer n = 200 ,其可以容易地适用于更大的值。

以下是参考算法的组合解释:

让我们从一个包含 {1, 2, 3} ,按其总和分组:

 index (sum)    partitions        count
     0           ()                 1
     1           (1)                1 
     2           (2)                1
     3           (1+2), (3)         2
     4           (1+3)              1
     5           (2+3)              1
     6           (1+2+3)            1

假设我们要构造一个包含 {1, 2, 3, 4} 请注意 {1, 2, 3} 也是 {1, 2, 3, 4} 不 包括 4 ,以及那些。我们可以做的是从上表开始,复制它,然后用 4. .这是你的桌子 {1, 2, 3, 4} :

 index (sum)   partitions        count
     0          ()                 1
     1          (1)                1 
     2          (2)                1
     3          (1+2), (3)         2
     4          (1+3), [4]         2
     5          (2+3), [1+4]       2
     6          (1+2+3),[2+4]      2
     7          [1+2+4],[3+4]      2
     8          [1+3+4]            1
     9          [2+3+4]            1
    10          [1+2+3+4]          1

包括的所有子集 4. 4. 正好是由括号包围的旧子集之一。我们可以重复此过程并为 {1,2,..,5} , {1,2,..,6} 等

但是我们实际上不需要存储实际的子集/分区,我们只需要每个索引/和的计数。例如,如果使用表 {1, 2, 3} 仅使用计数,我们可以为 {1, 2, 3, 4} 每个 (index, count) 从旧表中配对,并添加 count 到的当前计数 index + 4 其思想是,如果 {1, 2, 3} 总计 3 ,然后加入 4. 对于这两个子集中的每一个子集,将为 7 .

考虑到这一点,下面是这个过程的Python实现:

def c(n):
    counts = [1]

    for k in range(1, n + 1):
        new_counts = counts[:] + [0]*k

        for index, count in enumerate(counts):
            new_counts[index + k] += count

        counts = new_counts

    return counts

我们从桌子开始 {} ,它只有一个子集——空集——和为零。然后,我们为 {1} 那么 {1, 2} {1,2,..,n} .完成后,我们将计算每个分区的 n ,因为 n 可以包括大于的整数 n .

现在,我们可以对代码进行两个主要优化:

1. 将表限制为仅包含以下项: n 因为这是我们感兴趣的。如果 index + k 超过 n 然后我们就忽略它。我们甚至可以预先为最终表分配空间,而不是在每次迭代中增加更大的表。

2. 如果我们仔细地向后迭代旧表,我们实际上可以更新它,而不是在每次迭代时从头开始构建新表 到位 而不会弄乱任何新值。

通过这些优化,您可以有效地从 the Mathematics answer 前面提到过,这是由生成函数驱动的。它运行在 O(n^2) 时间和时间 O(n) 空间下面是Python中的外观:

def c(n):
    counts = [1] + [0]*n

    for k in range(1, n + 1):
        for i in reversed(range(k, n + 1)):
            counts[i] += counts[i - k]

    return counts

def Q(n):
    "-> the number of subsets of {1,..,n} that sum to n."
    return c(n)[n]

def f(n):
    "-> the number of subsets of {1,..,n} of size >= 2 that sum to n."
    return Q(n) - 1