【C++】辞書式順序で集合のすべての部分集合を生成するプログラム

本記事では、与えられた集合（配列）のすべての部分集合を辞書式順序（lexicographic order）で生成して出力するC++プログラムを紹介します。このアルゴリズムは、配列として与えられた集合から、要素数ごとの可能な組み合わせをすべて昇順に出力します。時間計算量は O(n×2ⁿ) です。

アルゴリズムの流れ

Begin
    各長さ「i」について GenAllSubset() 関数を呼び出します。
    1) GenAllSubset() の中で、currLen が reqLen より大きい場合はそのまま戻ります。
    2) そうでなければ、currLen が reqLen と等しいときに新しい部分集合が完成したことになるため、それを出力します。
    3) start を true として、currLen と s をそれぞれインクリメントした値で GenAllSubset() を再帰的に呼び出します。
    それ以外の場合は、start を false として、s をインクリメントした値で GenAllSubset() を再帰的に呼び出します。
End

サンプルコード

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

// 配列を昇順にソートする関数
void Sorting(vector<int>& a) {
    for (size_t i = 0; i < a.size(); i++) {
        for (size_t j = i + 1; j < a.size(); j++) {
            if (a[i] > a[j]) {
                swap(a[i], a[j]);
            }
        }
    }
}

// 長さ reqLen のすべての組み合わせを再帰的に生成する関数
void GenAllSubset(const vector<int>& a, int reqLen, int s,
                  int currLen, vector<bool>& check) {
    int len = a.size();
    if (currLen > reqLen)
        return;
    else if (currLen == reqLen) {
        cout << "\t";
        cout << "{ ";
        for (int i = 0; i < len; i++) {
            if (check[i]) {
                cout << a[i] << " ";
            }
        }
        cout << "}\n";
        return;
    }
    if (s == len)
        return;
    check[s] = true;   // s番目の要素を選ぶ場合
    GenAllSubset(a, reqLen, s + 1, currLen + 1, check);
    check[s] = false;  // s番目の要素を選ばない場合
    GenAllSubset(a, reqLen, s + 1, currLen, check);
}

int main() {
    int n;
    cout << "配列の要素数を入力してください: ";
    cin >> n;

    vector<int> arr(n);
    vector<bool> ch(n, false);

    for (int i = 0; i < n; i++) {
        cout << i + 1 << " 番目の要素を入力してください: ";
        cin >> arr[i];
    }

    Sorting(arr); // 昇順にソートして出力を辞書式順序に対応させる

    cout << "\n辞書式順序で並べた集合のすべての部分集合:\n";
    cout << "\t{ }\n"; // 空集合を出力
    for (int i = 1; i <= n; i++) {
        GenAllSubset(arr, i, 0, 0, ch);
    }
    return 0;
}

コードのポイント

• Sorting(): 入力された配列を昇順にソートすることで、出力全体が辞書式順序になります。
• GenAllSubset(): 再帰呼び出しによって各要素を「選ぶ／選ばない」の2通りで分岐させ、check[] 配列で選択状態を管理します。
• main(): まず空集合 { } を出力し、その後、長さ 1 から n まで順に GenAllSubset() を呼び出してすべての部分集合を生成します。

実行例（出力）

配列の要素数を入力してください: 6
1 番目の要素を入力してください: 3
2 番目の要素を入力してください: 2
3 番目の要素を入力してください: 1
4 番目の要素を入力してください: 7
5 番目の要素を入力してください: 6
6 番目の要素を入力してください: 5

辞書式順序で並べた集合のすべての部分集合:
{ }
{ 1 }
{ 2 }
{ 3 }
{ 5 }
{ 6 }
{ 7 }
{ 1 2 }
{ 1 3 }
{ 1 5 }
{ 1 6 }
{ 1 7 }
{ 2 3 }
{ 2 5 }
{ 2 6 }
{ 2 7 }
{ 3 5 }
{ 3 6 }
{ 3 7 }
{ 5 6 }
{ 5 7 }
{ 6 7 }
{ 1 2 3 }
{ 1 2 5 }
{ 1 2 6 }
{ 1 2 7 }
{ 1 3 5 }
{ 1 3 6 }
{ 1 3 7 }
{ 1 5 6 }
{ 1 5 7 }
{ 1 6 7 }
{ 2 3 5 }
{ 2 3 6 }
{ 2 3 7 }
{ 2 5 6 }
{ 2 5 7 }
{ 2 6 7 }
{ 3 5 6 }
{ 3 5 7 }
{ 3 6 7 }
{ 5 6 7 }
{ 1 2 3 5 }
{ 1 2 3 6 }
{ 1 2 3 7 }
{ 1 2 5 6 }
{ 1 2 5 7 }
{ 1 2 6 7 }
{ 1 3 5 6 }
{ 1 3 5 7 }
{ 1 3 6 7 }
{ 1 5 6 7 }
{ 2 3 5 6 }
{ 2 3 5 7 }
{ 2 3 6 7 }
{ 2 5 6 7 }
{ 3 5 6 7 }
{ 1 2 3 5 6 }
{ 1 2 3 5 7 }
{ 1 2 3 6 7 }
{ 1 2 5 6 7 }
{ 1 3 5 6 7 }
{ 2 3 5 6 7 }
{ 1 2 3 5 6 7 }

計算量について

n 個の要素を持つ集合には合計 2ⁿ 個の部分集合が存在し、それぞれの出力に最大 O(n) の処理が必要となるため、このアルゴリズムの時間計算量は O(n×2ⁿ) となります。要素数が増えると部分集合の数は指数関数的に増加するため、大きな n に対しては注意が必要です。