python-3.x - 如何找到加起来等于给定总和的索引和组合?
问题描述
如何找到加到给定 sum 的组合和相应的索引?而且,是否可以处理大小为 500000(更大)的元素列表?
输入:
l1 = [9,1, 2, 7, 6, 1, 5]
target = 8
**Constraints**
1<=(len(l1))<=500000
1<=each_list_element<=1000
输出:
Format : {index:element}
{1:1, 5:1, 4:6} #Indices : 1,5,4 Elements : 1,1,6
{1:1, 2:2, 6:5}
{5:1, 2:2, 6:5}
{1:1, 3:7}
{5:1, 3:7}
{2:2, 4:6}
试过:
from itertools import combinations
def test(l1, target):
l2 = []
l3 = []
if len(l1) > 0:
for r in range(0,len(l1)+1):
l2 += list(combinations(l1, r))
for i in l2:
if sum(i) == target:
l3.append(i)
return l3
l1 = [9,1, 2, 7, 6, 1, 5]
target = 8
print(test(l1,target))
[(1, 7), (2, 6), (7, 1), (1, 2, 5), (1, 6, 1), (2, 1, 5)]
有人可以指导我吗?
更新
Apart from above, code fails to handle these scenarios
Input = [4,6,8,5,3]
target = 3
Outputs {} , need to output {4:3}
Input = [4,6,8,3,5,3]
target = 3
Outputs {} , need to output {5:3,3:3} #corrected index
Input = [1,2,3,15]
target = 15
Outputs = {}, need to output {3:15}
解决方案
你的代码很接近,我会使用 enumerate 来获取索引和值作为元组对。我总是删除任何值大于目标的索引和值元组,因为这不可能是匹配的。这将产生更少的组合。然后像你一样,我只是遍历元组的排列并对每个排列中的值求和,如果它总和为目标,则产生该排列。最后在循环中输出我给 dict 的值以转换成你想要的 dict 格式
from itertools import combinations
def find_sum_with_index(l1, target):
index_vals = [iv for iv in enumerate(l1) if iv[1] < target]
for r in range(1, len(index_vals) + 1):
for perm in combinations(index_vals, r):
if sum([p[1] for p in perm]) == target:
yield perm
l1 = [9, 1, 2, 7, 6, 1, 5]
target = 8
for match in find_sum_with_index(l1, target):
print(dict(match))
输出
{1: 1, 3: 7}
{2: 2, 4: 6}
{3: 7, 5: 1}
{1: 1, 2: 2, 6: 5}
{1: 1, 4: 6, 5: 1}
{2: 2, 5: 1, 6: 5}
推荐阅读
- javascript - 如何在网页中触发从后台脚本到脚本的功能?
- amazon-cloudformation - AWS CloudFormation GetAtt 在 Fn::Sub 下不起作用
- python - 如何同时写入和读取 JSON 文件
- android - Firebase 扩展在 Firestore 中翻译文本不允许添加多个输入和输出字段
- javascript - 在 React 中推送到数组,意外行为
- php - 如何在 laravel 中编写套接字服务器?
- c++ - QT getSaveFileUrl方法复制默认文件名
- html - Django-Site 不显示使用 Django admin (ImageField) + Pillow 上传的图片
- java - 我的 Java 程序中没有更新余额
- python - 从特定用户导入推文并排除转推