Bit全探索（ビット全探索）とは
Bit全探索 とは、
です。
集合にn 個の要素があるとすると、全ての部分集合を列挙するためには \( 2^{n}\)回の操作が必要です。
これをbit全探索では、それぞれのビットが要素の選択・非選択を表すようにします。
例えば、集合{A, B, C} の要素数は3なので、 \( 2^{3} = 8\) 通りの部分集合が存在します。
各部分集合をビット列として表すと次のようになります。
| ビット列 | 部分集合 |
| 000 | ∅(空集合) |
| 001 | {A} |
| 010 | {B} |
| 011 | {A, B} |
| 100 | {C} |
| 101 | {A, C} |
| 110 | {B, C} |
| 111 | {A, B, C} |
特徴
長所
短所
実装(Python)
実装
S = ['A', 'B', 'C']
N = len(S)
for bit in range(1 << N):
subset = []
for i in range(N):
if bit & (1 << i): # i 番目の要素が選択されているか判定
subset.append(S[i])
print(f"{bit:03b}: {subset}")000: []
001: ['A']
010: ['B']
011: ['A', 'B']
100: ['C']
101: ['A', 'C']
110: ['B', 'C']
111: ['A', 'B', 'C']
参考文献
コメント