查找具有 n 不同部分的整数分区的数量

Question

具有

n

不同部分的整数分区是总和为

n

的正整数递减列表，其中没有数字出现超过一次。

例如，有 3 个 5 的整数分区：

[5], [4,1], [3,2]

。

编写一个函数，返回具有

n

不同部分的整数分区的数量，其中

1 <= n <= 600

。

来源：https://www.codewars.com/kata/6267a007e67fba0058725ad2

我写了这段代码：

import itertools
list_poss = [list(i) for j in range(1, n+1) for i in itertools.combinations(range(n+1), j) if sum(list(i)) == n and 0 not in list(i)]

但它太慢并给出以下错误：

Execution Timed Out (12000 ms)

。

如何进一步优化这段代码？

Answer 1

这看起来像是递归的工作。

n

的分区将始终拥有自己的 [n]。然后，对于从 n-1 到 n 的一半（不包括）的每个数字 k，可以用 k 和 n 的其余部分（即 n-k）形成分区：

from functools import lru_cache

@lru_cache(None)        # remember/reuse past results
def countParts(n):
    return 1 + sum(countParts(n-k) for k in range(n-1,n//2,-1))

输出：

for n in range(1,20):
    print(n,countParts(n))

1 1
2 1
3 2
4 2
5 3
6 3
7 5
8 5
9 7
10 7
11 10
12 10
13 13
14 13
15 18
16 18
17 23
18 23
19 30

countParts(100) # 4914

countParts(600) # 38847071

要查看分区是什么，您可以使用相同的逻辑编写递归生成器：

def genParts(n):
    yield [n]
    for k in range(n-1,n//2,-1):
        for p in genParts(n-k):
            yield [k,*p]

for n in range(1,10):
    print(n,*genParts(n))

1 [1]
2 [2]
3 [3] [2, 1]
4 [4] [3, 1]
5 [5] [4, 1] [3, 2]
6 [6] [5, 1] [4, 2]
7 [7] [6, 1] [5, 2] [4, 3] [4, 2, 1]
8 [8] [7, 1] [6, 2] [5, 3] [5, 2, 1]
9 [9] [8, 1] [7, 2] [6, 3] [6, 2, 1] [5, 4] [5, 3, 1]