Wolfram 数学世界:
P(n, k) 表示将 n 写为恰好 k 项之和的方式的数量,或者等价地,表示划分为其中最大恰好为 k 的部分的数量。(注意,如果“exactly k”改成“k or less”,“largest is just k”改成“no element大于k”,则得到配分函数q。)例如,P(5 , 3) = 2,因为长度为 3 的 5 的分区是 {3, 1, 1} 和 {2, 2, 1},最大元素为 3 的 5 的分区是 {3, 2} 和 {3, 1, 1}。
...
P(n, k) 可以从递归关系中计算出来
P(n, k) = P(n-1, k-1) + P(nk, k)
(Skiena 1990, p. 58; Ruskey)对于k > n,P(n, k) = 0,P(n, n) = 1 和 P(n, 0) = 0。
因此,如果我们想计算将 n 写成总和的方式的数量,我们应该计算 -

让我们定义 P(n, k):
def p(n, k):
"""Gives the number of ways of writing n as a sum of exactly k terms or, equivalently,
the number of partitions into parts of which the largest is exactly k.
"""
if n < k:
return 0
if n == k:
return 1
if k == 0:
return 0
return p(n-1, k-1) + p(n-k, k)
现在我们可以将写作方式的数量计算n
为总和:
n = 6
partitions_count = 0
for k in range(n + 1):
partitions_count += p(n, k)
print(partitions_count)
# Output:
# 11
作为p(n, k)
递归函数,您可以通过将每个值保存p(n, k)
在字典中来提高速度(感谢基于哈希的快速搜索!)并在计算之前检查我们是否计算了值(检查值是否在字典中) :
dic = {}
def p(n, k):
"""Gives the number of ways of writing n as a sum of exactly k terms or, equivalently,
the number of partitions into parts of which the largest is exactly k.
"""
if n < k:
return 0
if n == k:
return 1
if k == 0:
return 0
key = str(n) + ',' + str(k)
try:
temp = dic[key]
except:
temp = p(n-1, k-1) + p(n-k, k)
dic[key] = temp
finally:
return temp
全功能:
def partitions_count(n):
"""Gives the number of ways of writing the integer n as a sum of positive integers,
where the order of addends is not considered significant.
"""
dic = {}
def p(n, k):
"""Gives the number of ways of writing n as a sum of exactly k terms or, equivalently,
the number of partitions into parts of which the largest is exactly k.
"""
if n < k:
return 0
if n == k:
return 1
if k == 0:
return 0
key = str(n) + ',' + str(k)
try:
temp = dic[key]
except:
temp = p(n-1, k-1) + p(n-k, k)
dic[key] = temp
finally:
return temp
partitions_count = 0
for k in range(n + 1):
partitions_count += p(n, k)
return partitions_count
有用的网址: