Iterate over lists with a particular sum

Question

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

Can the element values just be `1` and `-1`? – gtlambert Jan 21 '16 at 17:47 — gtlambert, Jan 21 '16 at 17:47

Joran Beasley · Accepted Answer · 2016-01-21T18:16:33.133

7

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

edited Jan 21 '16 at 18:16

answered Jan 21 '16 at 17:54

Joran Beasley

110,522
12
160
179

1

`itertools.permutations` will still produce a ton of duplicates. It'd be better to use `itertools.combinations` to choose 11 positions for the -1s. – user2357112 Jan 21 '16 at 17:56
1

Note that it'd be `itertools.combinations(xrange(n), n//2-1)`, and then placing the -1s into the chosen positions. We wouldn't call `combinations` on `a_solution`. – user2357112 Jan 21 '16 at 17:57
ahh dang ... now I gotta go open a python interpretter – Joran Beasley Jan 21 '16 at 17:58
oh I see it makes sense now ... @user2357112 it just took me a minute to understand what you were saying – Joran Beasley Jan 21 '16 at 18:00
1

More generally, given an even `n` (>= 2): `a_solution = [-1] * (n//2 - 1) + [1] * (n//2 + 1)`. – jub0bs Jan 21 '16 at 18:01
1

(Also, you should probably use a number other than 25. 11+13=24. We need an even length here.) – user2357112 Jan 21 '16 at 18:02
at @user2357112 lol man thanks ... you helped make my answer much more right than it initially was :P – Joran Beasley Jan 21 '16 at 18:04
That gives me the error `Too many indices for array`. Shouldn't you have to loop over the indices? – SirParselot Jan 21 '16 at 18:10
apparently numpy doesnt like tuples ... change it to a list and it should work (see updated code) – Joran Beasley Jan 21 '16 at 18:16

comingstorm · Answer 2 · 2016-01-21T19:21:35.663

1

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]

edited Jan 21 '16 at 19:21

answered Jan 21 '16 at 17:52

comingstorm

25,557
3
43
67

1

I think you want `or` instead of `||` ... also this will almost guaranteed exceed pythons recursion stack limit (+1 all the same since it will work fine with smaller lists... and it explains well what the OP should do from a conceptual level) – Joran Beasley Jan 21 '16 at 18:08

Iterate over lists with a particular sum

2 Answers2

Linked