Generating binary lists that sum to a given number

Question

I am attempting Project Euler #15, which essentially reduces to computing the number of binary lists of length 2*size such that their entries sum to size, for the particular case size = 20. For example, if size = 2 there are 6 such lists: [1,1,0,0], [1,0,1,0], [1,0,0,1], [0,1,1,0], [0,1,1,0], [0,1,0,1], [0,0,1,1]. Of course the number of such sequences is trivial to compute for any value size and is equal to some binomial coefficient but I am interested in explicitly generating the correct sequences in Python. I have tried the following:

import itertools

size = 20

binary_lists = itertools.product(range(2), repeat = 2*size)

lattice_paths = {lists for lists in binary_lists if sum(lists) == size}

but the last line makes me run into memory errors. What would be a neat way to accomplish this?

Isn't this basically the same as asking "how many ways can I place *size* 1's in *2\*size* slots?" — NightShadeQueen, Aug 31 '15 at 14:48
@NightShadeQueen: Not if you want to see all of those ways listed. — Scott Hunter, Aug 31 '15 at 14:49

score 1 · Accepted Answer · answered Aug 31 '15 at 14:55

1

There are far too many for the case of size=20 to iterate over (even if we don't materialize them, 137846528820 is not a number we can loop over in a reasonable time), so it's not particularly useful.

But you can still do it using built-in tools by thinking of the positions of the 1s:

from itertools import combinations

def bsum(size):
    for locs in combinations(range(2*size), size):
        vec = [0]*(2*size)
        for loc in locs:
            vec[loc] = 1
        yield vec

which gives

>>> list(bsum(1))
[[1, 0], [0, 1]]
>>> list(bsum(2))
[[1, 1, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 0, 1], [0, 0, 1, 1]]
>>> sum(1 for x in bsum(12))
2704156
>>> factorial(24)//factorial(12)**2
2704156

answered Aug 31 '15 at 14:55

DSM

342,061
65
592
494

Although for *size* = 20 this seems to be taking a very long time to compute... Way more than the "1-minute rule" they have over at Project Euler. I can't really think of a neater solution, however. – A.P. Sep 02 '15 at 16:32
I don't understand. In the very first sentence of this answer, I remind you that there are way too many to iterate over. This is not how you're intended to solve Euler #15. For that, you should either (1) use the combinatorial formula, or (2) use dynamic programming. Many Euler problems have a brute force solution which takes forever, and might even work in the example, but will fail on the real problem. – DSM Sep 02 '15 at 16:39

score 0 · Answer 2 · answered Aug 31 '15 at 14:51

I'm not 100% sure of the math on this problem, but your last line is taking a generator and dumping it into a list, and based on your example, and your size of 20, that is a massive list. If you want to sum it, just iterate, but I don't think you can get a nice view of every combo

Generating binary lists that sum to a given number

2 Answers2

Linked