長さMで要素は0または1であるリストを全て列挙する

Question

タイトルの通り長さMが与えられたとき要素が0または1のリストを全て列挙したいです．

M = 10
padding = '0' + str(M) + 'b'
arrays = []
for i in range(2 ** M):
    binary = format(i, padding)
    binary_array = [int(binary[j]) for j in range(len(binary))]
    arrays.append(binary_array)

これで実際に実装はできました．
しかし，Mの値が大きくなると計算量が多く，このコードは現実的でありません．
もっと効率的な方法はありますか．

Comments

[hayataka2049]

何のためにこれを行いたいのですか？　目的によってはより適切な解法が存在するかもしれません。
（どのみち2**Mの長さのlistを作るのは非効率です）

Answer 1

itertools.product同様にジェネレータにすればメモリ使用量は減ります。

def bit_pattern(n):
    for i in range(2**n):
        yield [(i >> b) & 1 for b in range(n - 1, -1, -1)]

M = 10
for bit in bit_pattern(M):
    print(bit)

処理内容によっては、バイナリのままrangeにしておいて、必要なときに2進配列化する手もあるのでは？
itertool.product で処理した方が高速ですけど。

>>> M = 10
>>> pattern = range(1<<M)
>>> def to_array(b, n):
...     return [(i >> b) & 1 for b in range(n - 1, -1, -1)]
...
>>> print(to_array(pattern[5], M))
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1]

とか

>>> M = 10
>>> for i in range(2**M):
...     print(f"{i:0{M}b}")
... 
0000000000
0000000001
...
1111111110
1111111111

Answer 2

こんにちは

速くするために

• 文字列を経由しない。
• ビット演算を使う。（2で割るときに/ 2 ではなく右シフトする、など）

といった工夫をすることで、以下でどうでしょう？

M = 10

arrays = [[i >> j & 0b1 for j in reversed(range(M))] for i in range(2 ** M)]

• 動作確認用 Replt.it: https://repl.it/@jun68ykt/Q232173

参考になれば幸いです。

（※ビット演算を使ったコードは、shiracamusさんのご回答で既に提示されていましたので、別の方法を下記に追記しました。）

追記

1または0を要素とするリストを引数に取る、次のような関数incrementを考えます。

• たとえば、[0, 1, 0, 1] というリスト a があったとして、この a　を引数に与えられると、 a の要素の並びを２進数とみたてて、1を加えた結果のビットの並びを表す [0, 1, 1, 0] に変更し、変更後の a を返します。ただし、 [1, 1, 1, 1] が与えられたときは、リストの長さは変更されず、 [0, 0, 0, 0] にして返します。

このような increment は一例として再帰を使って以下のように書けます。（再帰を使わなくても書けるでしょう）

def increment(lis, length=None):
    if length is None:
        length = len(lis)
    if length == 0:
        return

    if lis[length-1]:
        lis[length-1] = 0
        increment(lis, length-1)
    else:
        lis[length-1] = 1

    return lis

上記の incrementを使うと、ご質問の arrays は、以下で得られます。

M = 10
a = [1] * M
arrays = [increment(a).copy() for _ in range(2 ** M)]

• 動作確認用 Replt.it: https://repl.it/@jun68ykt/Q232173-2

Answer 3

速いかどうか確認してませんが、コンパクトに書いてライブラリに任せるとすると、

import itertools

M=5
iter=itertools.product(*([[0,1]]*M))
print(list(iter))

リスト化せずに、イテレータのままで扱うとよいと思います。

Comments

[otn]

Rubyなら、
[0,1].repeated_permutation(M)
と、そのためのメソッド(重複ありの順列)があります。

[shiracamus]

productならrepeat引数も便利です。
import itertools
M = 10
arrays = list(itertools.product([0,1], repeat=M)

[otn]

ああ、そういう引数があったんですね。
補足ありがとうございます。