Creating an array of numbers that sum to a given number

Question

I've been working on some quick and dirty scripts for doing some of my chemistry homework, and one of them iterates through lists of a constant length where all the elements sum to a given constant. For each, I check if they meet some additional criteria and tack them on to another list.

I figured out a way to meet the sum criteria, but it looks horrendous, and I'm sure there's some type of teachable moment here:

# iterate through all 11-element lists where the elements sum to 8.
for a in range(8+1):
 for b in range(8-a+1):
  for c in range(8-a-b+1):
   for d in range(8-a-b-c+1):
    for e in range(8-a-b-c-d+1):
     for f in range(8-a-b-c-d-e+1):
      for g in range(8-a-b-c-d-e-f+1):
       for h in range(8-a-b-c-d-e-f-g+1):
        for i in range(8-a-b-c-d-e-f-g-h+1):
         for j in range(8-a-b-c-d-e-f-g-h-i+1):
            k = 8-(a+b+c+d+e+f+g+h+i+j)
            x = [a,b,c,d,e,f,g,h,i,j,k]
            # see if x works for what I want

[vals for vals in itertools.product(range(8), repeat=11) if sum(vals) == 8] is more beautiful, but much slower than your solution. — eumiro
– eumiro, Commented Mar 7, 2012 at 8:18
+1 - Props for using a computer to automate your repetitive chemistry homework. — Li-aung Yip
– Li-aung Yip, Commented Mar 7, 2012 at 9:21
My insight is this: for a list of 11 integers all summing to 8, a LOT of the numbers are going to be zero. A fast way of doing this would be to find all the ways of summing integers to 8 - for example 8, 1+7, 2+6, 3+5, 4+4, 1+1+6, 1+2+5... and then just permute those with the appropriate number of zeroes. — Li-aung Yip
– Li-aung Yip, Commented Mar 7, 2012 at 9:36

Janne Karila · Accepted Answer · 2012-03-09 06:50:48Z

1

Here's a recursive generator that yields the lists in lexicographic order. Leaving exact as True gives the requested result where every sum==limit; setting exact to False gives all lists with 0 <= sum <= limit. The recursion takes advantage of this option to produce the intermediate results.

def lists_with_sum(length, limit, exact=True):
    if length:
        for l in lists_with_sum(length-1, limit, False):
            gap = limit-sum(l)
            for i in range(gap if exact else 0, gap+1):
                yield l + [i]
    else:
        yield []

edited Mar 9, 2012 at 6:50

answered Mar 7, 2012 at 12:45

Janne Karila

25.3k6 gold badges60 silver badges97 bronze badges

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

Comments

Johannes Charra · Accepted Answer · 2012-03-07 09:17:45Z

1

Generic, recursive solution:

def get_lists_with_sum(length, my_sum):
    if my_sum == 0:
        return [[0 for _ in range(length)]]

    if not length:
        return [[]]
    elif length == 1:
        return [[my_sum]]
    else:
        lists = []
        for i in range(my_sum+1):
            rest = my_sum - i
            sublists = get_lists_with_sum(length-1, rest)
            for sl in sublists:
                sl.insert(0, i)
                lists.append(sl)

    return lists

print get_lists_with_sum(11, 8)

answered Mar 7, 2012 at 9:17

Johannes Charra

30k6 gold badges45 silver badges54 bronze badges

5 Comments

Li-aung Yip Over a year ago

Just tried running that. Oh my, that's slow... Maybe convert to something that uses a stack instead of full-blown recursion?

Johannes Charra Over a year ago

It's targeted at low values, of course. For the given numbers, i think it's acceptable. Building a cache into it will probably help, because the arguments will repeat quite often. Still the number of possible combinations will explode for higher valued arguments.

Li-aung Yip Over a year ago

With arguments 8,11 it redlined my CPU for a good few minutes before I killed it. OP's answer is actually very fast (just ugly.)

Li-aung Yip Over a year ago

And yes, memoizing it would probably help immensely.

Li-aung Yip Over a year ago

Hurp. I must have done something funny (I tried the lazy man's way of running it from an interactive Python shell.) I'll try it again when I get to work tomorrow.

Collectives™ on Stack Overflow

Creating an array of numbers that sum to a given number

2 Answers 2

Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related