【C++】バイナリカウント法で集合の部分集合をすべて生成するプログラムの実装方法

この記事では、バイナリカウント法（Binary Counting Method）を用いて、集合のすべての部分集合を生成するC++プログラムを紹介します。

バイナリカウント法の基本的な考え方

n 個の要素を持つ集合の部分集合の総数は 2^n 個になります。0 から 2^n − 1 までの各整数を n 桁の2進数で表すと、各ビットが「対応する要素を部分集合に含める（1）か、含めない（0）か」を表すことになります。この性質を利用すれば、2進数を1ずつ増やしていくだけで、すべての部分集合を漏れなく列挙できます。

アルゴリズム

Begin
    配列の要素を入力として受け取る。
    関数 BinaryCounting()：
        r = pow(2, n) により部分集合の総数を計算する（n は要素数）。
        0 から r-1 までの2進数を生成する。
        n 文字の各2進数文字列に対して solution() を呼び出す。
End

サンプルコード

#include<iostream>
#include<math.h>
using namespace std;
void solution(char code[], int a[], int n) //部分集合を出力する関数
{
    int i;
    cout<<"\t { ";
      for(i = 0; i < n; i++) {
         if(code[i] == '1')
            cout<<a[i]<<" ";
      }
    cout<<"}\n";
}
int BinaryCounting(int a[], int n) {
    int r, i, l;
    char bin[] = "00000";
    r = pow(2, n);
    //0 から r-1 までの2進数を生成する。
    for(i = 0; i < r; i++) {
       solution(bin, a, n);
       l=n-1;
       h:
       if(bin[l] == '0')
          bin[l] = '1';
       else {
          bin[l] = '0';
          l--;
          goto h;
       }
    }
}
int main() {
    int i, n;
    cout<<"\nEnter the number of elements: ";
    cin>>n;
    int a[n];
    cout<<"\n";
    for(i = 0; i < n; i++) {
       cout<<"Enter "<<i+1<<" element: ";
       cin>>a[i];
    }
    cout<<"\nThe subset in the binary counting method: \n";
    BinaryCounting(a, n);
    return 0;
}

実行結果

Enter the number of elements: 4
Enter 1 element: 4
Enter 2 element: 3
Enter 3 element: 2
Enter 4 element: 1
The subset in the binary counting method:
{ }
{ 1 }
{ 2 }
{ 2 1 }
{ 3 }
{ 3 1 }
{ 3 2 }
{ 3 2 1 }
{ 4 }
{ 4 1 }
{ 4 2 }
{ 4 2 1 }
{ 4 3 }
{ 4 3 1 }
{ 4 3 2 }
{ 4 3 2 1 }

コードのポイント

1. ビット列と部分集合の対応

文字列 bin の各文字が配列 a の各要素に対応しており、文字が '1' の位置の要素だけが部分集合に含まれます。たとえば 0101 であれば、1番目と3番目の要素を含む部分集合が出力されます。

2. 2進数のインクリメント処理

ループのたびに、最下位ビットから見ていき、'0' なら '1' に変更して終了、'1' なら '0' に戻して桁上がりを繰り返すことで、通常の2進数カウントと同じ動作を実現しています。

3. 計算量

部分集合は 2^n 個存在するため、計算量は O(2^n × n) となります。要素数が増えると出力が爆発的に増加する点には注意が必要です。