CODEWITHSUNDEEP
pythonmathoptimization
Simd
Simd

Reputation: 21223

Iterate over lists with a particular sum

I would like to iterate over all lists of length n whose elements sum to 2. How can you do this efficiently? Here is a very inefficient method for n = 10. Ultimately I would like to do this for `n > 25'.

n = 10
for L in itertools.product([-1,1], repeat = n):
    if (sum(L) == 2):
        print L #Do something with L

Upvotes: 4

Views: 172

Answers (2)

comingstorm
comingstorm

Reputation: 26107

One way is to stop your product recursion whenever the remaining elements can't make up the target sum.

Specifically, this method would take your itertools.product(...,repeat) apart into a recursive generator, which updates the target sum based on the value of the current list element, and checks to see if the resulting target is achievable before recursing further:

def generate_lists(target, n):
  if(n <= 0):
    yield []
    return
  if(target > n or target < -n):
    return
  for element in [-1,1]:
    for list in generate_lists(target-element, n-1):
      yield list+[element]

Upvotes: 1

Joran Beasley
Joran Beasley

Reputation: 113978

you only can have a solution of 2 if you have 2 more +1 than -1 so for n==24

a_solution = [-1,]*11 + [1,]*13

now you can just use itertools.permutations to get every permutation of this

for L in itertools.permutations(a_solution): print L

it would probably be faster to use itertools.combinations to eliminate duplicates 

for indices in itertools.combinations(range(24),11):
    a = numpy.ones(24)
    a[list(indices)] = -1
    print a

note for you to get 2 the list must be an even length

Upvotes: 7

Related Questions