如何找到加起来等于给定总和的索引和组合? [英] How to find indices and combinations that adds upto given sum?

问题描述

如何找到加起来等于给定总和的组合和相应的索引? 而且，是否可以处理大小为500000(较大大小)的元素的列表?

How to find the combinations and corresponding indices that adds upto given sum ? And also, can it be handled list of elements of size 500000 (higher size) ?

输入:

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格式

Your code was close, i would use enumerate to get the index and value as tuple pairs. I am always dropping any of the index and value tuples where that value is greater than the target since that cannot possible be a match. this will generate less combinations. Then like you i just iterate through the permutations of tuples and sum the values in each permutation, if it sums to the target then yield that permutation. lastly in the loop to output the values i give the perm to dict to convert into the dict format you wanted

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}

这篇关于如何找到加起来等于给定总和的索引和组合?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！