任意の集合のすべての部分集合を列挙する

　任意の集合について、すべての部分集合を列挙したい。これはつまり、ある集合から冪集合を作りたい、と言い換えられる。

　たとえば 3 つの要素からなる集合 X = {1, 2, 3} に対してP(X) = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }であるような写像 P を考えるとき、 P(X) は X の冪集合である。

　冪集合の要素数について、引用する。

　一般に X が n 個の元から成る有限集合ならば、P(X) は 2ⁿ 個の元をもつ集合となる（松坂 18¹）.

　証明については専門書に譲るとして、われわれが扱う集合は常に有限集合であるとしよう。先ほどの X = {1, 2, 3} と、そこから導かれる P(X) = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} } について、 X は 3 個の元をもつのに対して、 P(X) が 2³ 個の元をもつことは明らかである。これは要するに、 「その元を部分集合に含むかどうか」の二者択一を、 X の各元について判定している、と解釈すればいいことになる。

　さて、これを C++ でどう実装するか？

ビット列と部分集合を対応させる

　X の要素数と同じ長さのビットを考える。たとえば、 X = {A1, A2, A3} のときに、ビット長3のデータを考え、各ビットに各要素を対応させていくとすれば、 X の部分集合はビット列と一意に対応させることができ、その対応表は次のようになる。なお、順番の便宜上、2⁰の位にA1を、2¹の位にA2を、2²の位にA3を対応づけている。

000 : {}
001 : {A1}
010 : {A2}
011 : {A1, A2}
100 : {A3}
101 : {A1, A3}
110 : {A2, A3}
111 : {A1, A2, A3}

　このようにビット列の各桁を真偽値に見立て、ある桁にフラグが立っていればその桁に対応する要素を含む部分集合を作るというやり方で、冪集合の全要素を列挙できる。もちろん、このやり方で X = {A1, A2, A3, ..., AN} のように、添字づけられた有限集合に一般化できる。競技プログラミングではbit全探索と呼ばれるテクニックだという。計算量は元の集合の濃度を N として O(2^N) である。

#include<iostream>
using namespace std;

void print_power_set(int *a, int len) {
  for (int i = 0; i < (1<<len); i++) {
    for (int j = 0; j < len; j++) {
      if (i & (1 << j)) cout << a[j] << " ";
    }
    cout << endl;
  }
}

int main() {
  int a[] = {1, 2, 3, 4};
  print_power_set(a, 4);
  return 0;
}

---

1. 松坂和夫. 集合・位相入門. 岩波書店. ISBN978-4000298711.↩