将整数划分为集合的元素
将整数划分为集合的元素
提问于 2017-10-08 18:49:33
我想要定义一个函数，当给定一个集合(正整数)和一个整数时，它将该整数的分区数返回到集合的元素中。例如,
partitions({1,2,3},5)=5自从1+1+1+1+1=5，1+1+1+2=5，1+2+2=5，1+1+3=5和2+3=5之后。
在Python中实现这一功能的最有效方法是什么？
注意:它不需要返回实际的分区，只需要返回它们的数量。
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-10-08 19:08:56
如果这些值是积分和正(所以在set {1, 2, 3, ...}中)，我们可以在这里使用动态编程方法：
import numpy as np
def count_subsetsum(xs : set, s : int):
v = np.zeros(s+1, dtype=int)
v[0] = 1
for x in xs:
b = np.zeros(s+1, dtype=int)
b[:] = v[:]
for d in range(x,s+1,x):
b[d:] += v[:s-d+1]
v = b
return v[s]在这里，我们考虑向量v。最初，向量只包含零，除非v[0]等于1 (因为我们可以构造完全为零的一个和:不考虑任何元素)。
现在我们将更新矢量。我们将从可迭代的x中获取一个值xs，我们将“对向量进行求和”。我们通过迭代地将v[:s-d+1]添加到向量b的末尾来实现这一点。v[:s-d+1]包含(不包括) s-d-1的所有元素。我们将其添加到b[d:]中。因此，v[i]的值被添加到向量中的所有元素的b[i+d]中。在d的每一个倍数中，我们都会这样做。因此，第一次升级，我们实际上是“添加一个x”到v中的每个元素。第二次，我们在我们已经构造的每个和中“添加一个两个xs”。
我们对xs中的每一个v[s]都这样做，在最后v[s]包含了所有方法，我们可以构造一个与s相加的和。所以我们返回那个v[s]。
例如：
>>> count_subsetsum({1,2,3},5)
5 # 1+1+1+1+1 1+1+1+2 1+1+3 1+2+2 2+3
>>> count_subsetsum({1,2},5)
3 # 1+1+1+1+1 1+1+1+2 1+2+2
>>> count_subsetsum({1,3},5)
2 # 1+1+1+1+1 1+1+3
>>> count_subsetsum({1,3,5},5)
3 # 1+1+1+1+1 1+1+3 5
>>> count_subsetsum({1,2,4},5)
4 # 1+1+1+1+1 1+1+1+2 1+2+2 1+4
>>> count_subsetsum({1},5)
1 # 1+1+1+1+1(我为每个示例添加了一个注释，并给出了相应的总数)
使用动态规划法比蛮力法的优点是它不会成倍地缩放。例如，以下查询：
>>> count_subsetsum({1,2,5,7,22},15921)
1746490921624那是1'746'490'921'624。即使我们能够每秒产生10亿个结果，仍然需要1746秒(大约半个小时)。所以通常计数比枚举要快。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/46634824
复制相关文章
相似问题
腾讯云开发者
