与えられた文字列から生成できる全ての文字列（任意の長さ）を列挙する方法

この記事では、与えられた文字列から構成できる任意の長さのすべての文字列を生成する方法を解説します。これは、各文字の組み合わせ(部分列)とその順列をすべて求める問題です。

例えば、入力文字列が「ABC」の場合、次のような文字列が生成されます。

{A, B, C, AB, BA, BC, CB, CA, AC, ABC, ACB, BAC, BCA, CAB, CBA}

それでは、具体的な手順を見ていきましょう。

アルゴリズムの考え方

基本的なアイデアは次の通りです。

• 長さ n の文字列に対して、ビットフラグを用いて 2ⁿ - 1 通りの部分列を作成します(カウンタの j ビット目が立っていれば、j 番目の文字を選択)。
• それぞれの部分列に対して next_permutation を使って順列をすべて出力します。

擬似コード

Begin
    n := 文字列 str の長さ
    count := 2^n - 1
    for カウンタ = 0 to count, do
        sub_str := 空文字列
        for j = 0 to n-1, do
            if カウンタの j ビット目が立っている場合
                sub_str に str の j 番目の文字を連結
            end if
        done
        repeat:
            sub_str を出力
        until sub_str の次の順列が存在しなくなるまで
    done
End

C++による実装例

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
void printAllString(string str) {
    int n = str.size();
    unsigned int count = pow(2, n);
    for (int counter = 1; counter <count; counter++) { // 2^n - 1 個の文字列を生成
        string subs = "";
        for (int j = 0; j < n; j++) {
            if (counter & (1<<j)) // j ビット目が立っているとき、j 番目の文字を追加
                subs.push_back(str[j]);
        }
        do{
            cout << subs << endl;
        }
        while (next_permutation(subs.begin(), subs.end()));
    }
}

コードのポイント

• counter & (1 << j):ビット演算により、カウンタの j ビット目がセットされているかを判定し、対応する文字を部分列に追加します。
• next_permutation():標準ライブラリの関数で、同じ文字集合の並び替え(順列)を辞書順に次々と生成します。

実行結果(入力:ABCD)

A
B
AB
BA
C
AC
CA
BC
CB
ABC
ACB
BAC
BCA
CAB
CBA
D
AD
DA
BD
DB
ABD
ADB
BAD
BDA
DAB
DBA
CD
DC
ACD
ADC
CAD
CDA
DAC
DCA
BCD
BDC
CBD
CDB
DBC
DCB
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA

このように、入力文字列「ABCD」から長さ 1 の文字列から長さ 4 の文字列まで、すべての組み合わせと順列が出力されていることが確認できます。なお、文字数が増えると組み合わせの総数は指数関数的に増加するため、この手法は短い文字列に適しています。