python - 给定元素长度的 Python 子集和问题
问题描述
对于给定的集合,元素的总和和长度,
我想获取集合是否满足条件的布尔值
例如...
Input : set = [18,0,2,20], sum = 20, length = 2 <br>
Output : True (subset [18,2] satisfy the sum=20 for given length 2)
Input : set = [18,0,2,20], sum = 22, length = 1 <br>
Output : False
如果有给定的长度限制,我该如何解决这个问题?
(如果没有长度条件,我可以轻松解决:
subset-sum-problem)
def isSubsetSum(set, n, sum):
if sum == 0:
return True
if (sum != 0) and (n == 0):
return False
if (set[n-1] > sum):
return isSubsetSum(set,n-1,sum)
# (a) including the last element
# (b) excluding the last element
# Not "AND", But "OR" !!!!!
return isSubsetSum(set,n-1,sum) or isSubsetSum(set,n-1,sum-set[n-1])
解决方案
如果您被允许使用导入的模块,itertools有一个组合功能可以使这变得非常容易:
from itertools import combinations
set = [18,0,2,20]
total = 20
length = 2
result = [ c for c in combinations(set,length) if sum(c) == total ]
if result:
print("True, subset ",result[0],"satisfies the sum", total, "given length",length)
else:
print("False")
如果您需要它是一个递归函数,请考虑对于X
集合中的每个元素,如果您可以N-1
在后续元素中找到一个元素子集sum-X
,那么您就有一个解决方案sum/length=N
。
例如:
def subSum(numbers,total,length):
if len(numbers) < length or length < 1:
return []
for index,number in enumerate(numbers):
if length == 1 and number == total:
return [number]
subset = subSum(numbers[index+1:],total-number,length-1)
if subset:
return [number] + subset
return []
推荐阅读
- java - 尝试将 Json 存储在 DB 中时,Ebean 'No service implementation found for SpiJsonService'
- php - Postgres 查询在“where”处或附近给出语法错误
- github - 使用 GitHub 使页面上线
- angular - 如何在 Angular 2+ 中基于组件创建模板?
- python-3.x - 在 igraph 上使用 cairo 绘图时出错:模块 'cairo' 没有属性 'Surface'
- join - awk 匹配/比较/每个文件中的 2 列(对于 2 个文件)
- geocoding - 您已超出此 API 的每日请求配额。甚至使用 api 密钥
- spring - 无法代理接口实现方法 [public final void AbstractTestNGSpringContextTests.setApplicationContext()]
- vba - 通过输入框输入的数字未链接到我在 B 列中的公式
- ruby - 如何使用 selenium 网格对 appium 运行并行测试?