【C++】文字列のべき集合を辞書順に出力する方法を徹底解説

この記事では、C++を用いて、与えられた文字列の各文字を要素とするべき集合(冪集合)を辞書式順序(辞書順)で生成し、出力する方法を解説します。

べき集合とは?

べき集合(Power Set)とは、ある集合 S に含まれるすべての部分集合を要素とする集合のことで、一般的に P(S) と表記されます。

例：

S = {1, 2, 3};
P(S) = {{}, {1}, {1, 2}, {1, 3}, {2}, {2, 3}, {3}, {1, 2, 3}}

本問題では、文字列をひとつの集合として扱い、その各文字を集合の要素とみなします。また、空文字列(空集合)もべき集合の一部として含まれる点に注意してください。

問題の具体例

入力： str = "xyz"
出力： x xy xyz xz y yz z

解法のアプローチ

辞書順に出力するためには、まず文字列をあらかじめソートしておく必要があります。そのうえで、次の手順で部分集合を生成していきます。

1. 文字列の中から 1 文字を固定します。
2. 残りの文字に対して再帰的に関数を呼び出し、すべての部分集合を生成します。
3. 先頭で固定した文字を取り除くことで、次の組み合わせ(順列)を取得します。

この手法により、重複のない完全なべき集合を効率よく列挙できます。部分集合の総数は 2ⁿ 個(n は文字列の長さ)となるため、全体の時間計算量は O(n × 2ⁿ) 程度となります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

// すべての部分集合を出力する再帰関数
void printAllSubsets(string str, int n, int index = -1, string subset = "") {
    if (index == n)
        return;
    cout << subset << "\n";
    for (int i = index + 1; i < n; i++) {
        subset += str[i];
        printAllSubsets(str, n, i, subset);
        subset = subset.erase(subset.size() - 1);
    }
    return;
}

// べき集合を生成する関数
void GeneratePowerSet(string str) {
    sort(str.begin(), str.end());   // 辞書順になるよう事前にソート
    printAllSubsets(str, str.size());
}

int main() {
    string str = "xyz";
    cout << "Power Set of the string '" << str << "' is :\n";
    GeneratePowerSet(str);
    return 0;
}

コードのポイント

printAllSubsets 関数では、現在のインデックス以降の各文字を順に部分集合へ追加しながら再帰呼び出しを行います。再帰から戻った後、直前に追加した文字を erase で削除することで、別の組み合わせの探索に備えています。これにより、空文字列から始まるすべての部分集合が漏れなく出力されます。

実行結果

Power Set of the string 'xyz' is :
x xy xyz xz y yz z

まとめ

本記事では、文字列を集合とみなし、そのべき集合を辞書順に出力する C++ プログラムを紹介しました。ポイントは「事前のソート」と「再帰による部分集合の生成」の 2 点です。同様のアプローチは、配列やリストの部分集合列挙など、さまざまな組み合わせ問題にも応用できるので、ぜひ参考にしてください。