How to limit Python recursive combinations?

Question

I am currently trying to solve a how to get this piece of code to iterate through the different combinations of numbers below to equal 1200. Which works fine however I want the code to limit the numbers it explores and print the combinations with only 5 different numbers.

E.g1 70, 260, 280, 290, 300 = 1200, uses 5 numbers. I want only these combinations.

E.g2 10, 20, 30, 40, 110, 120, 160, 190, 240, 280 = 1200, uses 10 numbers. I don't want combinations with less than five or greater than 5, like this combination.

I don't know python too well, I feel like its a simple thing to do but with my limited coding knowledge I'm stuck.

#!/usr/local/bin/python
from itertools import combinations

def find_sum_in_list(numbers, target):
    results = []
    for x in range(len(numbers)):
        results.extend(
            [   
                combo for combo in combinations(numbers ,x)  
                    if sum(combo) == target    
            ]
    )
    print results

if __name__ == "__main__":
    find_sum_in_list([10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300], 1200)

Thanks for any help. Much appreciated.

Two things: 1) I can't see how your function is recursive. It doesn't call itself. 2) If you only want combinations of 5 elements, why loop through different values of x and ask for combinations of x elements? — Marius
– Marius, Commented Nov 16, 2014 at 23:48
sorry this kind of math is beyond me. I tried putting 5 into x and it does work. I needed someone to point it out me before I could see my mistake. Thanks. — Metori
– Metori, Commented Nov 16, 2014 at 23:54

Eric · Accepted Answer · 2014-11-16 23:47:21Z

1

I think that combinations second argument is the number of items to combine. Try passing 5 instead of x

answered Nov 16, 2014 at 23:47

Eric

19.9k20 gold badges89 silver badges151 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

jack · Accepted Answer · 2014-11-17 00:03:46Z

1

You actually have almost what you need. The two lines in your list comprehension are pretty much everything, except for using '5' instead of 'x', as @Eric says. If you use filter to weed out all the combinations that don't have the right sum, then you end up with:

from itertools import combinations

def find_sum_in_list(numbers, target):
    return filter(lambda x: sum(x) == target, combinations(numbers, 5))

if __name__ == '__main__':
    print find_sum_in_list(range(10, 310, 10), 1200)

filter takes a function that takes each element of a list and returns true or false. I've passed into it an anonymous function that returns true only if the list sums to the target.

I also used range to generate your list of numbers, by counting from 10 to 310 by 10. range excludes the last element.

edited Nov 17, 2014 at 0:03

answered Nov 16, 2014 at 23:57

jack

2,2141 gold badge21 silver badges17 bronze badges

3 Comments

Metori Over a year ago

That's a clever method thanks. However I wanted to run other combinations of numbers some with duplicates so there might be two 10's or three 30's. I don't think I can do that with this method as its a range rather than discrete numbers.

jack Over a year ago

You're welcome. You can use this find_sum_in_list implementation though. That isn't specific to my use of range.

Metori Over a year ago

Sorry my mistake :P. I wasn't reading your code closely enough.

AtlasMeh-ed · Accepted Answer · 2014-11-17 01:21:29Z

0

You are on the right track but I don't think you need to do something recursive. I think this works.

from itertools import combinations

def find_sum_in_list(numbers, target, comboSize):
    results = []
    for combo in combinations(numbers, comboSize):
        if sum(combo) == target:
            results.append(combo)
    return results


if __name__ == "__main__":
    numbers = [10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300]
    total = 1200
    comboSize = 5
    print find_sum_in_list(numbers, total, comboSize)

edited Nov 17, 2014 at 1:21

answered Nov 16, 2014 at 23:57

AtlasMeh-ed

4775 silver badges7 bronze badges

3 Comments

Metori Over a year ago

Thanks this code looks good too. You've written it very clearly too so its easier for me to understand.

AtlasMeh-ed Over a year ago

@Metori No problem. You can definitely make it short with an answer like jack's but it sounded like understandably was important. Don't forget to upvote the answers you like and accept.

jack Over a year ago

Only problem with this solution is the extra loop in the main block. He only needs five-number combinations, and this gives him more.

oopcode · Accepted Answer · 2014-11-16 23:55:22Z

0

Well, it is not less recursive than your code, but I think it kind of does what you want.

import itertools

target_list = [
    10, 20, 30, 40, 50, 60, 70, 80, 
    90, 100, 110, 120, 130, 140, 150, 
    160, 170, 180, 190, 200, 210, 220, 
    230, 240, 250, 260, 270, 280, 290, 300
]

target_sum = 1200

def find_sum(target_list, num_elem, target_sum):
    combinations = itertools.combinations(target_list, num_elem)

    for comb in combinations:
        if sum(comb) == target_sum:
            print comb


find_sum(target_list, 5, target_sum)

answered Nov 16, 2014 at 23:55

oopcode

1,9722 gold badges17 silver badges29 bronze badges

1 Comment

Metori Over a year ago

I really like your method too. It seems very fast at spitting out the combinations.

Collectives™ on Stack Overflow

How to limit Python recursive combinations?

4 Answers 4

Comments

3 Comments

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

3 Comments

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related