CODEWITHSUNDEEP
python
Adamso
Adamso

Reputation: 107

a function that returns number of sums of a certain number.py

I need to write a function that returns the number of ways of reaching a certain number by adding numbers of a list. For example:

print(p([3,5,8,9,11,12,20], 20))
should return:5

The code I wrote is:

def pow(lis):
    power = [[]]
    for lst in lis:
        for po in power:
            power = power + [list(po)+[lst]]
    return power

def p(lst, n):
    counter1 = 0
    counter2 = 0
    power_list = pow(lst)
    print(power_list)
    for p in power_list:
        for j in p:
            counter1 += j
        if counter1 == n:
            counter2 += 1
            counter1 == 0
        else:
            counter1 == 0
    return counter2

pow() is a function that returns all of the subsets of the list and p should return the number of ways to reach the number n. I keep getting an output of zero and I don't understand why. I would love to hear your input for this. Thanks in advance.

Upvotes: 0

Views: 181

Answers (4)

B. M.
B. M.

Reputation: 18668

A one pass solution with one counter, which minimize additions. 

def one_pass_sum(L,target):
   sums = [0]
   cnt = 0
   for x in L:
       for y in sums[:]: 
           z = x+y
           if z <= target : 
                sums.append(z)
                if z == target : cnt += 1
   return cnt

This way if n=len(L), you make less than 2^n additions against n/2 * 2^n by calculating all the sums.

EDIT :

A more efficient solution, that just counts ways. The idea is to see that if there is k ways to make z-x, there is k more way to do z when x arise. 

def enhanced_sum_with_lists(L,target):
    cnt=[1]+[0]*target # 1 way to make 0
    for x in L:
        for z in range(target,x-1,-1):  # [target, ..., x+1, x]
            cnt[z] += cnt[z-x]
    return cnt[target]

But order is important : z must be considered descendant here, to have the good counts (Thanks to PM 2Ring).

This can be very fast (n*target additions) for big lists.

For example : 

>>> enhanced_sum_with_lists(range(1,100),2500)
875274644371694133420180815

is obtained in 61 ms. It will take the age of the universe to compute it by the first method.

Upvotes: 1

PM 2Ring
PM 2Ring

Reputation: 55499

As tobias_k and Faibbus mentioned, you have a typo: counter1 == 0 instead of counter1 = 0, in two places. The counter1 == 0 produces a boolean object of True or False, but since you don't assign the result of that expression the result gets thrown away. It doesn't raise a SyntaxError, since an expression that isn't assigned is legal Python.

As John Coleman and B. M. mention it's not efficient to create the full powerset and then test each subset to see if it has the correct sum. This approach is ok if the input sequence is small, but it's very slow for even moderately sized sequences, and if you actually create a list containing the subsets rather than using a generator and testing the subsets as they're yielded you'll soon run out of RAM.

B. M.'s first solution is quite efficient since it doesn't produce subsets that are larger than the target sum. (I'm not sure what B. M. is doing with that dict-based solution...).

But we can enhance that approach by sorting the list of sums. That way we can break out of the inner for loop as soon as we detect a sum that's too high. True, we need to sort the sums list on each iteration of the outer for loop, but fortunately Python's TimSort is very efficient, and it's optimized to handle sorting a list that contains sorted sub-sequences, so it's ideal for this application.

def subset_sums(seq, goal):
    sums = [0]
    for x in seq:
        subgoal = goal - x
        temp = []
        for y in sums:
            if y > subgoal:
                break
            temp.append(y + x)
        sums.extend(temp)
        sums.sort()
    return sum(1 for y in sums if y == goal)

# test

lst = [3, 5, 8, 9, 11, 12, 20]
total = 20
print(subset_sums(lst, total))

lst = range(1, 41)
total = 70
print(subset_sums(lst, total))

output

5
28188

With lst = range(1, 41) and total = 70, this code is around 3 times faster than the B.M. lists version.

Upvotes: 1

Faibbus
Faibbus

Reputation: 1133

There are two typos in your code: counter1 == 0 is a boolean, it does not reset anything.

This version should work:

def p(lst, n):
    counter2 = 0
    power_list = pow(lst)       
    for p in power_list:
        counter1 = 0 #reset the counter for every new subset
        for j in p:
            counter1 += j
        if counter1 == n:
            counter2 += 1
    return counter2

Upvotes: 1

abcabc
abcabc

Reputation: 61

from itertools import chain, combinations

def powerset_generator(i):
    for subset in chain.from_iterable(combinations(i, r) for r in range(len(i)+1)):
        yield set(subset)

def count_sum(s, cnt):
    return sum(1 for i in powerset_generator(s) if sum(k for k in i) == cnt)

print(count_sum(set([3,5,8,9,11,12,20]), 20))

Upvotes: 0

Related Questions