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
– NightShadeQueen, Commented Aug 31, 2015 at 14:48
@NightShadeQueen: Not if you want to see all of those ways listed. — Scott Hunter
– Scott Hunter, Commented Aug 31, 2015 at 14:49

DSM · Accepted Answer · 2015-08-31 14:55:27Z

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, 2015 at 14:55

DSM

355k67 gold badges606 silver badges504 bronze badges

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

2 Comments

A.P. Over a year ago

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.

DSM Over a year ago

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.

AndrewGrant · Accepted Answer · 2015-08-31 14:51:39Z

0

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

answered Aug 31, 2015 at 14:51

AndrewGrant

8089 silver badges17 bronze badges

Collectives™ on Stack Overflow

Generating binary lists that sum to a given number

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related