CODEWITHSUNDEEP
python
Nick T
Nick T

Reputation: 26717

Creating an array of numbers that sum to a given number

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

Upvotes: 5

Views: 381

Answers (2)

Janne Karila
Janne Karila

Reputation: 25197

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 []

Upvotes: 1

Johannes Charra
Johannes Charra

Reputation: 29913

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)

Upvotes: 1

Related Questions