Pythonで（0,1）の組み合わせのリストを作成する方法はありますか？

Question

私はものにリストを作成したいことは、次のようにゼロの組み合わせの場所に挿入します。私はrepeatのパラメータが20ほど大きくなったときに、しかし

[e for e in itertools.product(range(2), repeat=6) if sum(e)==2] 

を使用して、リストを構築することができます

l = [(0, 0, 0, 0, 1, 1), 
    (0, 0, 0, 1, 0, 1), 
    (0, 0, 0, 1, 1, 0), 
    (0, 0, 1, 0, 0, 1), 
    (0, 0, 1, 0, 1, 0), 
    (0, 0, 1, 1, 0, 0), 
    (0, 1, 0, 0, 0, 1), 
    (0, 1, 0, 0, 1, 0), 
    (0, 1, 0, 1, 0, 0), 
    (0, 1, 1, 0, 0, 0), 
    (1, 0, 0, 0, 0, 1), 
    (1, 0, 0, 0, 1, 0), 
    (1, 0, 0, 1, 0, 0), 
    (1, 0, 1, 0, 0, 0), 
    (1, 1, 0, 0, 0, 0)] 

、コードは非常に時間がかかります。

私は、中間結果をメモリに蓄積することが問題だと思いましたか？ 私は必要なリストを作成するためのよりよい方法があることを知りたいと思います。おかげさまで

Answer 1

非再帰的な方法は大きなNでうまくいくかもしれませんが、少し理解しやすいかもしれません - 単にkビットをアクティブにすることを選択します。私

In [43]: list(bits_on(6, 2)) 
Out[43]: 
[(1, 1, 0, 0, 0, 0), 
(1, 0, 1, 0, 0, 0), 
(1, 0, 0, 1, 0, 0), 
(1, 0, 0, 0, 1, 0), 
(1, 0, 0, 0, 0, 1), 
(0, 1, 1, 0, 0, 0), 
(0, 1, 0, 1, 0, 0), 
(0, 1, 0, 0, 1, 0), 
(0, 1, 0, 0, 0, 1), 
(0, 0, 1, 1, 0, 0), 
(0, 0, 1, 0, 1, 0), 
(0, 0, 1, 0, 0, 1), 
(0, 0, 0, 1, 1, 0), 
(0, 0, 0, 1, 0, 1), 
(0, 0, 0, 0, 1, 1)] 

と

In [46]: %time len(list(bits_on(200,2))) 
CPU times: user 132 ms, sys: 0 ns, total: 132 ms 
Wall time: 131 ms 
Out[46]: 19900 

In [47]: %time len(list(choose(200,2))) 
CPU times: user 9.4 s, sys: 0 ns, total: 9.4 s 
Wall time: 9.4 s 
Out[47]: 19900 

In [48]: set(bits_on(200,2)) == set(choose(200,2)) 
Out[48]: True 

Answer 2

次の関数は、k個のすべてのnタプルのリストを返します。それは例えば、choose(50,2)ための第二の分割で動作します：

def choose(n, k): 
    if n < k or k < 0: 
     return [] 
    elif n == 0: 
     return [()] 
    return \ 
     [(0,) + r for r in choose(n-1, k)] + \ 
     [(1,) + r for r in choose(n-1, k-1)] 

次はchoose(6,2)の出力です：

>>> choose(6,2) 
[(0, 0, 0, 0, 1, 1), 
(0, 0, 0, 1, 0, 1), 
(0, 0, 0, 1, 1, 0), 
(0, 0, 1, 0, 0, 1), 
(0, 0, 1, 0, 1, 0), 
(0, 0, 1, 1, 0, 0), 
(0, 1, 0, 0, 0, 1), 
(0, 1, 0, 0, 1, 0), 
(0, 1, 0, 1, 0, 0), 
(0, 1, 1, 0, 0, 0), 
(1, 0, 0, 0, 0, 1), 
(1, 0, 0, 0, 1, 0), 
(1, 0, 0, 1, 0, 0), 
(1, 0, 1, 0, 0, 0), 
(1, 1, 0, 0, 0, 0)] 

これは、問題の例と同じです。