如何找到加起来等于给定总和的指数和组合?

Question

如何找到组合和相应的索引，加起来就是给定的总和？ 而且，可以处理大小为 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}

Answer 1

你的代码很接近，我会使用 枚举来获取元组对的索引和值。我总是删除任何值大于目标的索引和值元组，因为这不可能是匹配的。这将生成较少的组合。然后像你一样，我只是遍历元组的排列并对每个排列中的值求和，如果它与目标求和，则产生该排列。最后在循环中输出我给 perm to 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}

Answer 2

您可以使用索引函数来获取索引，并在字典的帮助下将它们存储为键：值对，如下所示，

from itertools import combinations
def test(l1, target):
l2 = []
l3 = []
l4=[]
dict1={}
a=0
if len(l1) > 0:
for r in range(0,len(l1)+1):        
l2 += list(combinations(l1, r))
for i in l2:
dict1={}
if sum(i) == target:
for j in i:
a=l1.index(j)
dict1[a]=j
l4.append(dict1)
l3.append(i)
return l4
l1 = [4,6,8,5,3]
target = 3
print(test(l1,target))

输出：

[{4: 3}]

如您所见，l1 = [4,6,8,5,3] target = 3工作的条件以前不起作用。

希望这有帮助！