【C++】和集合が元の集合になる部分集合ペアをすべて生成するプログラム

本記事では、2つの部分集合の和集合がもとの集合（上位集合）と完全に一致するような、すべての部分集合ペアを生成するC++プログラムを紹介します。

基本的な考え方はシンプルです。各要素について「左の集合に入れるか」「右の集合に入れるか」の2択を考えることで、n個の要素から 2^(n-1) 通りのペアが導き出せます。どのペアを選んでも、2つの集合を足し合わせれば必ずもとの集合に戻る仕組みです。

アルゴリズム

開始
    関数 UnionSet():
    引数:
        a[] = 配列
        n = 要素数
    処理内容:
        1) 0 から 2^(n-1)-1 までの2進数コードを生成し、計 2^(n-1) 個のペアに対応させる。
        2) 各コードごとに、対応するインデックスが '1' の要素を一方の集合へ、'0' の要素をもう一方の集合へ振り分けて出力する。
        3) 出力された2つの集合の和集合は、必ずもとの集合（上位集合）と一致する。
終了

サンプルプログラム

#include<iostream>
#include<math.h>
#include<iomanip>
using namespace std;

void display(char code[], int a[], int n) // ペアを表示する関数
{
    int i;
    cout<<"\t{ ";
    for(i = 0; i < n; i++) {
        if(code[i] == '1')
            cout<<a[i]<<" ";
    }
    cout<<"}";
    cout<<"{ ";
    for(i = 0; i < n; i++) {
        if(code[i] == '0')
            cout<<a[i]<<" ";
    }
    cout<<"}\n";
}

void UnionSet(int a[], int n) {
    int i, r, l;
    char binary[n];
    r = pow(2, n-1);
    for(i = 0; i < n; i++)
        binary[i] = '0';
    for(i = 0; i < r; i++) {
        display(binary, a, n);
        l=n-1;
        h:
        if(binary[l] == '0')
            binary[l] = '1';
        else {
            binary[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 possible subset pairs which on union generates the superset, are: \n";
    UnionSet(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 possible subset pairs which on union generates the superset, are:
{ } { 4 3 2 1 }
{ 1 } { 4 3 2 }
{ 2 } { 4 3 1 }
{ 2 1 } { 4 3 }
{ 3 } { 4 2 1 }
{ 3 1 } { 4 2 }
{ 3 2 } { 4 1 }
{ 3 2 1 } { 4 }

コードの解説

このプログラムの核となるのは、UnionSet() 関数内で管理される binary[] という文字配列です。各要素が '0' または '1' を持つこの配列は、いわば2進数のカウンタとして機能します。

• '1' の位置の要素 … 左側の集合に出力
• '0' の位置の要素 … 右側の集合に出力

ループが1回まわるごとに、2進数のカウントアップと同じ要領で binary[] の値を更新していきます。最下位ビットから順に確認し、'0' なら '1' に、すでに '1' なら '0' に戻して桁上げを行う仕組みです。これにより、空集合と全体集合のペア { } { 4 3 2 1 } から始まり、すべての組み合わせが漏れなく列挙されます。

なお、要素数 n のとき生成されるペアの総数は 2^(n-1) 通りです。{ A }{ B } と { B }{ A } は順序違いの同一ペアとして重複を避けるため、半分の数だけ生成している点にも注目してください。