CODEWITHSUNDEEP
pythonlist
Ceiun
Ceiun

Reputation: 73

Check if elements in a list equal to the sum value of the list

I am trying to figure out a more pythonic way of accepting a list and enumerating through the list, checking whether the sum of a sequence of elements == to the sum of the whole list, if so, it will create a return a sub list.

Note: A solution for checking any combination of elements would be interesting too.

For example:

example1 = [8, 9, 10, 10, 10, -20]

Output = [8, 9, 10]

example2 = [-15, 6, 8, 2, 10, 10, -5]

Output = [6, 8, 2]

Upvotes: 1

Views: 1662

Answers (4)

Maurice Meyer
Maurice Meyer

Reputation: 18106

You could iterate over all combinations of list:

import itertools


def calc_sum(lst):
    res = []
    lst_sum = sum(lst)
    for L in range(1, len(lst)):
        for subset in itertools.combinations(lst, L):
            if sum(subset) == lst_sum:
                res.append(subset)
    print(set(res))


for item in ([8, 9, 10, 10, 10, -20], [-15, 6, 8, 2, 10, 10, -5]):
    calc_sum(item)

Edit: You just need to iterate for each list item to the end:

def calc_sum(lst):
    len_lst = len(lst)
    lst_sum = sum(lst)
    for i in range(0, len_lst):
        for j in range(i, len_lst):
            _subList = lst[i:j]
            if sum(_subList) == lst_sum:
                print(_subList)

Out:

{(8, 9, 10)}
{(6, 8, 2), (6, 10)}

Upvotes: 1

Nechoj
Nechoj

Reputation: 1582

Maybe I understood what you mean by only sequences:

import itertools


# https://docs.python.org/3/library/itertools.html#itertools-recipes
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)))


def is_sequence(iterable):
    """ checks if iterable is a sequence of number such as [5, 6, 7], irrespective of the order
    Uses the fact that sum([a, a+1, a+2, ..., a+n]) = n*(n+1)/2 + a*(n + 1)
    """
    n = len(iterable) - 1
    m = min(iterable)
    return max(iterable) - m == n and sum(iterable) == n*(n+1)/2 + m*(n + 1)


def find_subsets(ll: list, only_sequences=False):
    ll_sum = sum(ll)
    if only_sequences is True:
        return set([s for s in powerset(ll) if sum(s) == ll_sum and is_sequence(s)])
    else:
        return set([s for s in powerset(ll) if sum(s) == ll_sum])


print(find_subsets([6, 8, 9, 10, 10, -19], False))  # (6, 8, 9)
print(find_subsets([6, 8, 9, 10, 10, -19], True))   # empty set
print(find_subsets([7, 8, 9, 10, 10, -20], True))   # (7, 8, 9)

Upvotes: 0

Nechoj
Nechoj

Reputation: 1582

There is a pattern from itertools to find all subsets of a list. Using this pattern, a solution would be:

import itertools


# https://docs.python.org/3/library/itertools.html#itertools-recipes
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)))
    # return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s) + 1))


def find_subsets(ll: list):
    ll_sum = sum(ll)
    return set([s for s in powerset(ll) if sum(s) == ll_sum])


print(find_subsets([-15, 6, 8, 2, 10, 10, -5]))

# gives: [(6, 10), (6, 8, 2)]

Note that in the final result list there will be some double entries that eventually need to be filtered out. Also, the total list is a solution.

Upvotes: 0

Alain T.
Alain T.

Reputation: 42143

If you're only looking for consecutive sequences , you can use the accumulate() function (from itertools) to get cumulative sums and check if any difference between these sequential sums is equal to the total of the list. This will allow you to use a set to accelerate the process and get a near O(n) time complexity:

from itertools import accumulate
def seqSum(L):
   s = sum(L)
   a = [0,*accumulate(L)]  # sequential totals
   sa = set(a)             # accelerate matching using a set
   return  [ L[i:i+a[i+1:].index(v+s)+1] for i,v in enumerate(a)
             if v+s in sa and v+s in a[i+1:(None,-1)[i<1]]]

Output:

print(seqSum([8, 9, 10, 10, 10, -20]))    # [[8, 9, 10]]

print(seqSum([-15, 6, 8, 2, 10, 10, -5])) # [[6, 8, 2]]

print(seqSum([-15, 6, 8, 2, 10, -4, 10, 4, -5]))
# [[6, 8, 2], [8, 2, 10, -4], [10, -4, 10]]

Note that this will not find overlapping sequences that begin on the same element, so only one sequence (the shortest) can be obtained for each position in the list

Upvotes: 0

Related Questions