C++で集合のすべての部分集合（べき集合）を列挙する方法

この記事では、与えられた集合のすべての部分集合を表示する方法を解説します。例えば、集合が {1, 2, 3} である場合、その部分集合は {}, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3} の8種類になります。すべての部分集合を集めた集合は「べき集合（power set）」と呼ばれ、要素数 n の集合に対してべき集合は 2ⁿ 個の要素を持ちます。

アルゴリズムの考え方：ビット演算を活用

この問題はビット演算を使うと非常にシンプルに解けます。0 から 2ⁿ - 1 までの整数をカウンターとしてループ処理し、各反復でカウンターの i 番目のビットが立っている（1になっている）かどうかを確認します。ビットが立っていれば、その位置に対応する集合の i 番目の要素を出力します。

この方法では、各カウンターの値が「どの要素を部分集合に含めるか」を表すビットパターンとして機能するため、重複のないすべての部分集合を漏れなく列挙できます。

サンプルコード

#include<iostream>
#include<cmath>
using namespace std;

void showPowerSet(char *set, int set_length) {
    unsigned int size = pow(2, set_length);
    for(int counter = 0; counter < size; counter++) {
        cout << "{";
        for(int j = 0; j < size; j++) {
            if(counter & (1<<j))
                cout << set[j] << " ";
        }
        cout << "}" << endl;
    }
}

int main() {
    char set[] = {'a','b','c'};
    showPowerSet(set, 3);
}

実行結果

{}
{a }
{b }
{a b }
{c }
{a c }
{b c }
{a b c }

コードの解説

関数 showPowerSet では、まず pow(2, set_length) によってべき集合の要素数 2ⁿ を計算します。外側のループはカウンターを 0 から 2ⁿ - 1 まで進め、内側のループで各ビット位置 j を調べます。式 counter & (1<<j) が真であれば、j 番目のビットが立っていることを意味するため、集合の j 番目の要素を出力します。

例えば、カウンターが 5（バイナリで 101）のときは、ビット0とビット2が立っているため、部分集合 {a, c} が出力されます。

計算量

このアルゴリズムの時間計算量は O(n × 2ⁿ) です。部分集合の総数が 2ⁿ であり、それぞれの部分集合を構築するのに最大 n 回のビット判定が必要になるためです。べき集合は指数関数的に増加するため、n が大きくなると出力自体が膨大になる点に注意してください。