python - 生成总和为给定数字的二进制列表

Question

我正在尝试 Project Euler #15，它本质上减少了计算长度 2*size 的二进制列表的数量，使得它们的条目总和为 size，对于特殊情况大小= 20。例如，如果size = 2，则有 6 个这样的列表:[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]。当然，对于任何值 size 来说，计算此类序列的数量都是微不足道的，并且等于某个二项式系数，但我对在 Python 中显式生成正确的序列感兴趣。我尝试过以下方法:

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}

但是最后一行让我遇到了内存错误。什么是完成此任务的巧妙方法？

Answer 1

对于 size=20 的情况，需要迭代的次数太多(即使我们不具体化它们，137846528820 也不是我们可以在合理时间内循环的数字)，因此它不是特别有用。

但是您仍然可以使用内置工具通过考虑 1 的位置来完成此操作:

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

这给出了

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