ビットマスクによる部分集合列挙

n個の要素のすべての部分集合は、1つの整数に対応させられます。0から順に数えると、それぞれの数のビットが、どの要素を含めるかを正確に表します。🙂

n 個の要素からなる集合には、2^n 個の部分集合があります。そのため、整数を 0 から 2^n - 1 まで動かせば、すべての部分集合を一度ずつ訪問できます。

シフト演算 1 << n は、2 の n 乗と等しくなります。部分集合を列挙するループの上限を、簡潔かつ高速に表せます。

要素 i が部分集合に含まれるか調べるには、1 を i ビット左シフトした値とのビット演算で、そのビットを確認します。結果が 0 でなければ、その要素は含まれています。

各ビット位置を調べ、ビットが立っている要素を集めます。これにより、1 つのマスクから、それが表す具体的な部分集合を作れます。

マスク 0 は空集合を表し、すべてのビットが 1 のマスクは全体集合を表します。ループですべての値を扱うため、どちらも自然に含まれます。

ループの中で、選択した要素を合計して各部分集合を評価します。これは多くの小規模な全探索解法の中心となる考え方です。

選択した要素の数は、マスクのpopcountと等しくなります。Python では bin(mask).count('1') ですぐに求められます。

部分集合は 2^n 個あるため、この方法は小さな n にしか適していません。すべて列挙する場合、実用上の上限は n が 20 前後です。

複雑な入れ子のループを 1 つの整数ループに置き換えられ、ビット演算も高速です。コードが短く明快になり、テストもしやすくなります。

maskをループし、ビットを解読して部分集合を評価し、最良の結果を記録します。このテンプレートを覚えておけば、多くの部分集合問題を定型的に解けます。

mask で表された部分集合に要素 i が含まれているかを調べたいとします。

0 から 2^n - 1 までmaskをループし、mask と 1 を i ビット左シフトした値でビットを読み取り、各部分集合を評価します。小さな n に対する、簡潔な全探索です。🚀