Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Python

Posted by amuhrlipiq
amuhrlipiq
1,995 Points

Python: combination calculator to targeted sum - validation step

Hi, everyone, I'm still struggling with this code. It's a number combination calculator to targeted sum. I need to add a validation step to see if the number already exists in my output list - if it exists then the code shouldn’t show this output. I try a lot of ideas, but I can’t solve it (for example if x in numbers etc.). 

def subset_sum(numbers, target, partial=[]):
    s = sum([int(x) for x in partial])
    numbers = [int(x.strip()) for x in combination.split(',')]
    if s == int(target):
        print("sum(%s)=%s" % (partial, int(target)))
    if s >= int(target):
        return
    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i + 1:]
        subset_sum(remaining, int(target), partial + [n])
combination = input("combination:   ")
target_sum = input("target:   ")
if __name__ == "__main__":
    subset_sum([combination], target_sum)

For example:

Input:

combination:   1, 2, 3
target:   3


Output:
sum([1, 1, 1])=3 ....<- this is what I dont want to show up
sum([1, 2])=3
sum([2, 1])=3
sum([3])=3

Just each number in input can be only once in output.

Thank you so much for the advice.

3 Answers

Jeff Muday
MOD
Jeff Muday
Treehouse Moderator 28,732 Points
Jeff Muday
Jeff Muday
Treehouse Moderator 28,732 Points

Below is the fastest program I can create. I wrote it without a function, so I would not have to pass around the permutations to save time.

I ran into a memory error when I went beyond permutations of length 10.

You might want to add an input to LIMIT the length of the permutations sets that are checked.

Are you coming up with some new theory on cryptocurrency? ;-)

from itertools import permutations

if __name__ == "__main__":
    print("Input combination of integers separated by commas")
    combination = input("combination:   ")
    target_sum = input("target:   ")

    # convert user input to a list of numbers (numlist)
    strlist = combination.split(',')
    numlist = []
    for item in strlist:
        numlist.append(int(item))

    # this is the new code
    for length in range(1,len(numlist) + 1):
        perms = list(permutations(numlist, length))
        print("checking {} permutations of length {}".format(len(perms), length))
        for p in perms:
            s = sum(p)
            if s == int(target_sum):
                print("sum({}) = {}".format(list(p), sum(p)))

    print('done.')

The output is a little different but is verbose so I can see how much work the computer has to do.

Input combination of integers separated by commas
combination:   1,2,3
target:   3
checking 3 permutations of length 1
sum([3]) = 3
checking 6 permutations of length 2
sum([1, 2]) = 3
sum([2, 1]) = 3
checking 6 permutations of length 3
done.

Look at this-- I gave it an impossible sum for the combination of numbers to illustrate growth rate of permutation sets. The two bullet points are:

1. There is an amazing number of calculations to perform.

2. Python itertools does not have a provision to "spool" the permutations to a file. So basically you end up holding 3.6 million lists in memory! Yikes!!

Input combination of integers separated by commas
combination:   1,2,3,4,5,6,7,8,9,10
target:   100
checking 10 permutations of length 1
checking 90 permutations of length 2
checking 720 permutations of length 3
checking 5040 permutations of length 4
checking 30240 permutations of length 5
checking 151200 permutations of length 6
checking 604800 permutations of length 7
checking 1814400 permutations of length 8
checking 3628800 permutations of length 9
checking 3628800 permutations of length 10
done.

Here's an online tool to calculate permutations so you can explore how much time/memory a permutation set of 30 might be!

https://www.calculatorsoup.com/calculators/discretemathematics/permutations.php

Good luck in your Python adventure!

amuhrlipiq
amuhrlipiq
1,995 Points

Oh my PC memory almost blow up :)))

I think that there have to be used generator with "yield" otherwise PC memory can't handle it. (Maybe?)

Or I was thinking that I need only the first combination of numbers equal to the target sum. So maybe the code could stop when it finds the first right combination. for example combination 1, 2, 3 target 3 ...output is 3 = 3 then the app stops.

Jeff Muday
MOD
Jeff Muday
Treehouse Moderator 28,732 Points
Jeff Muday
Jeff Muday
Treehouse Moderator 28,732 Points

You're welcome! These kind of problems are fun to solve.

You are right, the generate_all_permutations() gets out of hand quickly. There are some ways to use generator functions (you will learn about these later) to save iteration and memory overhead.

amuhrlipiq
amuhrlipiq
1,995 Points

Thank you for your advice. I will look at that functions generator. :)

amuhrlipiq
amuhrlipiq
1,995 Points

Jeff, I try to use generator instead list and It help me. But it still takes a lot of time when I use around 30 numbers in input. Is there any possibility to improve it? 

     def generate_all_permutatations(mylist):
     for i in range(1,len(mylist)+1):
     yield from permutations(mylist, r=i)
Jeff Muday
MOD
Jeff Muday
Treehouse Moderator 28,732 Points
Jeff Muday
Jeff Muday
Treehouse Moderator 28,732 Points

@Miroslav you must be a number theorist! I like where you were going with your solution.

Here is my interpretation of what you were trying to do.

You will probably be interested in using itertools.permutations

from itertools import permutations

def generate_all_permutatations(mylist):
    """generate all permutation groups of length 1 through length of entire list"""
    permset = set()
    for length in range(1,len(mylist)+1):
        permlist = list(permutations(mylist, length))
        for item in permlist:
            permset.add(item)
    return list(permset)


if __name__ == "__main__":
    print("Input combination of integers separated by commas")
    combination = input("combination:   ")
    target_sum = input("target:   ")

    # convert user input to a list of numbers (numlist)
    strlist = combination.split(',')
    numlist = []
    for item in strlist:
        numlist.append(int(item))


    print("Generate possible solutions of various lengths")
    my_permutations = generate_all_permutatations(numlist)
    print(my_permutations)

    print("Solutions to target_sum = {}".format(target_sum))
    for group in my_permutations:
        if sum(group) == int(target_sum):
            print("sum({}) = {}".format(list(group), sum(group)))

Here's a program run:

Input combination of integers separated by commas
combination:   1,2,3
target:   3
Generate possible solutions of various lengths
[(1, 2), (3, 2), (1, 3), (3, 1, 2), (1, 3, 2), (1,), (3, 2, 1), (2,), (3, 1), (3,), (2, 1), (1, 2, 3), (2, 3, 1), (2, 3), (2, 1, 3)]
Solutions to target_sum = 3
sum([1, 2]) = 3
sum([3]) = 3
sum([2, 1]) = 3

Here's another test

Input combination of integers separated by commas
combination:   1,2,4,6,7
target:   7
Generate possible solutions of various lengths
[(6, 4, 7, 1), (2, 7, 4, 6, 1), (7, 6, 4, 1), (2, 7, 6, 4, 1), (4, 1, 2, 7, 6), (6, 4, 7, 2), (6, 4, 2, 7, 1), (4, 7, 6), (4, 7, 1, 6), (7, 1, 4, 2), (2, 6, 1, 4), (6, 7, 1, 4), (1, 6), (6, 7, 2), (1, 4, 2), (2, 7, 4), (4, 1, 7, 6, 2), (6, 2, 1, 7), (4, 2, 7, 6, 1), (7, 2, 1), (4, 6, 1, 7), (4, 6, 7, 1), (6, 7, 1, 2), (2, 6, 7, 4, 1), (4, 6, 7, 2), (1, 7, 2), (2, 6, 7), (2, 1, 4, 7), (6, 7), (2, 7, 6), (7, 6, 2, 4), (7, 6, 2, 1), (4, 6, 1, 2, 7), (7, 2, 4, 6, 1), (7, 6), (7, 2, 6, 4, 1), (1, 2, 4, 7), (1, 6, 2, 7, 4), (6, 2, 7, 4, 1), (7, 4, 1), (2, 1, 6, 4), (6, 7, 4, 1, 2), (7,), (1, 7, 6), (1, 4, 2, 7, 6), (4, 2, 1, 7), (2, 6), (2, 7, 4, 6), (2, 1, 7, 6, 4), (4, 1, 7), (1, 6, 2, 7), (7, 4, 6, 1), (4, 7, 2, 1, 6), (1, 7, 4), (2, 6, 1), (1, 6, 2, 4), (1, 2, 7, 4, 6), (1, 4, 7, 6, 2), (4, 6, 1), (6, 1, 7, 4), (2, 7, 6, 1, 4), (4, 2, 6, 1, 7), (1, 2, 4), (4, 7, 1, 6, 2), (4, 2, 7, 6), (1, 2, 4, 6, 7), (1, 2, 6, 4, 7), (7, 2, 6, 1, 4), (6, 1, 7, 2), (7, 4, 2, 1), (2, 6, 4, 1, 7), (1, 2, 6), (6, 2, 4, 1), (2, 6, 1, 7, 4), (7, 6, 2), (1, 2, 7, 6), (2, 6, 7, 1, 4), (2, 4, 1, 7, 6), (2, 4, 7, 1, 6), (6, 2, 4, 1, 7), (4, 1, 7, 2), (6, 1, 4, 7, 2), (2, 4, 6, 1, 7), (6, 2, 1, 7, 4), (1, 7, 6, 2), (4, 6, 7), (6, 2, 7, 1, 4), (7, 1, 4, 6, 2), (7, 1, 6, 4, 2), (1, 4, 7, 2), (1, 7, 6, 4), (7, 6, 4, 1, 2), (7, 2, 1, 4), (2, 1), (6, 4, 1, 2), (4, 7, 2, 6, 1), (7, 6, 4), (4, 7, 6, 2, 1), (6, 4, 1, 7), (4, 6, 1, 7, 2), (4, 6, 7, 1, 2), (2, 1, 7, 6), (7, 2), (1,), (6, 2, 4), (6, 2, 7, 1), (6, 1, 2), (7, 1, 6, 2), (2, 6, 7, 4), (2, 7, 1, 4), (7, 6, 4, 2), (4, 7, 1, 2), (7, 1, 6, 4), (4, 1, 2, 6), (1, 6, 7, 4, 2), (6, 1, 2, 7), (1, 6, 4), (6, 4, 2), (4, 1), (4, 1, 6, 7), (6, 4, 1, 2, 7), (6, 4, 1, 7, 2), (6, 4, 7, 1, 2), (6, 4), (2, 1, 7), (6, 2, 1, 4), (1, 4, 2, 6), (7, 1), (1, 2, 6, 7), (1, 4, 6, 7), (2, 4, 6, 7), (2, 4, 6), (1, 2, 6, 4), (7, 4, 1, 6), (4, 6, 1, 2), (2, 1, 4, 7, 6), (2, 4, 6, 7, 1), (7, 2, 4, 1, 6), (7, 6, 2, 4, 1), (7, 6, 4, 2, 1), (6, 1, 4), (1, 2, 6, 7, 4), (2, 7, 6, 1), (4, 2, 1, 7, 6), (2, 7, 1, 4, 6), (4, 2, 7, 1, 6), (7, 4, 1, 2, 6), (1, 7, 2, 4, 6), (2, 7), (4, 2, 7), (1, 7, 4, 2, 6), (2, 7, 4, 1), (1, 6, 2), (4, 6), (4, 6, 7, 2, 1), (2,), (6, 1), (7, 2, 6), (7, 2, 4, 6), (7, 4, 6, 1, 2), (4, 2, 1), (7, 4), (7, 4, 6, 2), (7, 2, 4), (6, 4, 2, 7), (4, 7, 6, 1), (6, 1, 7, 2, 4), (6, 7, 1, 2, 4), (7, 6, 2, 1, 4), (4, 7, 6, 2), (1, 4, 7), (2, 7, 1), (4, 7, 1), (2, 6, 4, 7), (1, 6, 4, 7), (6, 7, 2, 1), (1, 7, 2, 6), (4, 1, 7, 2, 6), (6, 7, 1), (6, 4, 7, 2, 1), (4, 7, 2, 1), (7, 1, 2), (6, 2), (4, 1, 2, 6, 7), (4, 1, 6, 2, 7), (4, 2, 6, 7, 1), (4, 1, 6, 7, 2), (1, 2, 7, 4), (2, 4, 1, 6), (2, 6, 4, 7, 1), (2, 4, 7, 6), (4, 6, 2, 1, 7), (6, 7, 4, 1), (7, 1, 4, 2, 6), (6, 7, 4, 2), (7, 1, 6), (1, 6, 7, 2, 4), (6, 2, 4, 7, 1), (6, 7, 1, 4, 2), (2, 6, 4), (7, 4, 2), (7, 4, 2, 6, 1), (7, 4, 6, 2, 1), (7, 1, 4), (7, 1, 2, 6), (1, 7, 4, 6), (1, 4, 7, 2, 6), (6, 1, 4, 2, 7), (4, 1, 6), (2, 1, 6, 7, 4), (2, 1, 4, 6, 7), (2, 1, 6, 4, 7), (1, 4, 2, 6, 7), (1, 4, 6, 2, 7), (4, 7, 1, 2, 6), (1, 2, 4, 7, 6), (1, 4), (1, 4, 6, 7, 2), (2, 7, 1, 6, 4), (7, 4, 6), (4, 2, 1, 6, 7), (7, 2, 1, 6, 4), (1, 7, 2, 6, 4), (1, 7, 6, 2, 4), (4, 2), (4, 7, 6, 1, 2), (1, 6, 7, 2), (4, 1, 2), (2, 7, 1, 6), (6, 2, 7, 4), (4, 1, 2, 7), (2, 6, 1, 4, 7), (4, 2, 6, 1), (6, 1, 2, 4), (1, 6, 7, 4), (4, 6, 2), (2, 6, 1, 7), (1, 2, 7), (4, 2, 6, 7), (1, 4, 2, 7), (4, 1, 6, 2), (4,), (7, 1, 4, 6), (7, 4, 1, 2), (6, 2, 1, 4, 7), (6, 1, 7, 4, 2), (6, 7, 2, 4, 1), (6, 7, 4, 2, 1), (2, 4, 6, 1), (1, 7), (7, 1, 2, 4, 6), (2, 4, 1, 6, 7), (2, 1, 4, 6), (1, 4, 6, 2), (2, 4), (7, 6, 1), (4, 7), (1, 2, 4, 6), (7, 6, 1, 4, 2), (2, 1, 6, 7), (2, 7, 6, 4), (6, 2, 7), (4, 2, 1, 6), (6, 4, 7), (2, 4, 1), (7, 2, 4, 1), (1, 2), (7, 2, 6, 4), (6, 4, 1), (6, 4, 2, 1), (7, 2, 6, 1), (7, 4, 2, 6), (4, 2, 7, 1), (1, 6, 2, 4, 7), (1, 6, 4, 2, 7), (1, 6, 4, 7, 2), (2, 6, 4, 1), (4, 7, 2, 6), (1, 7, 2, 4), (2, 1, 6), (6, 2, 4, 7), (6, 2, 1), (1, 6, 4, 2), (6, 7, 2, 4), (6, 4, 2, 1, 7), (6, 7, 2, 1, 4), (2, 4, 1, 7), (2, 4, 7), (2, 4, 7, 1), (2, 1, 4), (2, 4, 7, 6, 1), (7, 6, 1, 2), (2, 1, 7, 4, 6), (6, 1, 7), (7, 2, 1, 4, 6), (1, 6, 7), (4, 1, 7, 6), (7, 6, 1, 4), (1, 2, 7, 6, 4), (7, 2, 1, 6), (2, 7, 4, 1, 6), (1, 4, 7, 6), (7, 4, 2, 1, 6), (1, 7, 4, 2), (4, 6, 2, 1), (4, 6, 2, 7, 1), (4, 2, 6), (7, 1, 2, 6, 4), (7, 1, 2, 4), (6, 7, 4), (7, 1, 6, 2, 4), (4, 6, 2, 7), (7, 4, 1, 6, 2), (2, 1, 7, 4), (1, 7, 4, 6, 2), (1, 7, 6, 4, 2), (4, 7, 2), (6, 1, 4, 2), (6,), (6, 1, 4, 7), (2, 6, 7, 1), (1, 4, 6), (6, 1, 2, 7, 4), (7, 6, 1, 2, 4), (6, 1, 2, 4, 7)]
Solutions to target_sum = 7
sum([1, 6]) = 7
sum([1, 4, 2]) = 7
sum([7]) = 7
sum([1, 2, 4]) = 7
sum([6, 1]) = 7
sum([4, 2, 1]) = 7
sum([4, 1, 2]) = 7
sum([2, 4, 1]) = 7
sum([2, 1, 4]) = 7
amuhrlipiq
amuhrlipiq
1,995 Points

Hi, Jeff, you are so amazing! I really appreciate it, I'm so happy for your solution, so much to learn from it. I heard about itertools for the first time.

This code shutdown my PC, it requires a lot of computing power. I will try it on the server, but it will probably run for a longer period of time when I set up many input numbers.

But you are really amazing! Thank you again.