C++で文字の重複を許して文字列の全順列を辞書順に出力する方法

この問題では、n 文字からなる文字列が与えられ、その文字列を構成する文字を使ったすべての順列を出力します。ここでは同じ文字の繰り返し(重複)が許されており、順列は辞書順(アルファベット順)で出力する必要があります。

問題の例

まず、具体例で内容を確認してみましょう。

入力: XY

出力: XX、XY、YX、YY

解き方:「固定して再帰する」アプローチ

この問題を解くには、「fix and recur(固定と再帰)」という考え方を利用します。手順は以下の通りです。

1. 結果用バッファの先頭の位置に、元の文字列から1文字を選んで固定します。
2. 残りの位置について、再帰的に同じ処理を呼び出して文字を埋めていきます。
3. 最後の位置まで埋まったら、その順列を出力します。

入力文字列が「XY」の場合の流れを見てみましょう。

• 先頭に「X」を固定 → X_
• 残りの位置を再帰的に埋める → XX → XY
• 次に先頭に「Y」を固定 → Y_
• 残りの位置を再帰的に埋める → YX → YY

このロジックは、長さ3、4、さらに一般の長さ n の文字列にもそのまま適用できます。なお、重複を許す場合、生成される順列の総数は nⁿ 個となるため、計算量は O(nⁿ) になります。

C++での実装例

#include <iostream>
#include <string.h>
using namespace std;

void printPermutations(char *str, char* permutations, int last, int index){
    int i, len = strlen(str);
    for (i = 0; i < len; i++) {
        permutations[index] = str[i];
        if (index == last)
            cout << permutations << "\t";
        else
            printPermutations(str, permutations, last, index + 1);
    }
}

int main() {
    char str[] = "ABC";
    cout << "All permutations of the string with repetition of " << str << " are: " << endl;
    int len = strlen(str);
    char permutations[len];
    printPermutations(str, permutations, len - 1, 0);
    return 0;
}

実行結果

All permutations of the string with repetition of ABC are:
AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC

コードのポイント

• printPermutations 関数は、現在埋めている位置(index)と最後の位置(last)を比較し、最後の位置に達した時点で順列を1つ完成させて出力します。
• 各位置に対して、元の文字列のすべての文字を試すため、自然に辞書順の出力順序になります(元の文字列がソート済みであることが前提です)。
• 再帰の深さは文字列の長さ分だけなので、スタックオーバーフローの心配はほとんどありません。

このように、シンプルな再帰処理を組み合わせるだけで、文字の重複を許すすべての順列を効率よく列挙できます。