вырабатывающих двоичные списки, сумму заданного числа

Question

Я пытающегося Проект Эйлера # 15, который по существу сводится к вычислению числа двоичных списков длины 2 * размер таким образом, что их записи подводить к размер, для конкретного кейс размер = 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]. Конечно, число таких последовательностей тривиально для вычисления для любого значения размера и равно некоторому биномиальному коэффициенту, но меня интересует явное генерирование правильных последовательностей в 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 для повторения (даже если мы не будем нажимать) t материализуют их, 137846528820 - это не число, которое мы можем зацикливать в разумные сроки), поэтому это не особенно полезно.

Но вы все еще можете сделать это с помощью встроенных инструментов, думая о позиции из 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 

, который дает

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

Answer 2

Я не уверен на 100% в математике по этой проблеме, но ваша последняя строка берет генератор и вбрасывает его в список, и на основе вашего примера и вашего размера 20, это массивный список , Если вы хотите его суммировать, просто повторите, но я не думаю, что вы можете получить прекрасный обзор каждого комбо.