【C++】重複する文字を含む文字列のすべての異なる順列を出力する方法

この問題では、重複する文字を含む可能性のある文字列が与えられます。求められているのは、その文字列から作られるすべての異なる順列（重複を除いた並べ替え）を出力することです。

問題の例

まず、具体的な入出力例を見てみましょう。

入力：string = "XYZ"
出力：XYZ XZY YXZ YZX ZYX ZXY

解き方の考え方

この問題を解くには、一つの要素を固定しながら残りの要素を入れ替えていく、いわゆる「辞書順に次の順列を生成する」アルゴリズムが有効です。大まかな流れは以下のとおりです。

1. 文字列全体を昇順にソートします。これが最初の（辞書順で最も小さい）順列になります。
2. 現在の順列を出力します。
3. 右端から走査し、「後ろの文字より小さい」となる最も右の位置 i を探します。
4. i より右側の範囲の中から、str[i] より大きい最小の文字（ceil）を見つけ、str[i] と入れ替えます。
5. i の右側の部分を再度ソートして、次の順列を完成させます。
6. 文字列が完全に降順になった（＝最後の順列に到達した）時点で終了します。

この手法の利点は、同じ並びが二度と生成されないことです。そのため、重複する順列を自動的に除外できます。

C++での実装例

上記の考え方を実装したプログラムが以下のとおりです。

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

// qsort 用の比較関数（昇順）
int compare(const void* a, const void* b) {
    return (*(char*)a - *(char*)b);
}

// 2つの文字を入れ替える補助関数
void swapChar(char* a, char* b) {
    char t = *a;
    *a = *b;
    *b = t;
}

// str[l..h] の中で first より大きい最小の文字（ceil）の位置を返す
int findCeil(char str[], char first, int l, int h) {
    int ceilIndex = l;
    for (int i = l + 1; i <= h; i++)
        if (str[i] > first && str[i] < str[ceilIndex])
            ceilIndex = i;
    return ceilIndex;
}

// すべての順列を辞書順に出力する
void printPermutations(char str[]) {
    int size = strlen(str);
    qsort(str, size, sizeof(str[0]), compare);  // まず昇順にソート
    bool isFinished = false;
    while (!isFinished) {
        cout << str << "\t";                    // 現在の順列を出力
        int i;
        // 右から「str[i] < str[i+1]」となる位置を探す
        for (i = size - 2; i >= 0; --i)
            if (str[i] < str[i + 1])
                break;
        if (i == -1)
            isFinished = true;                  // 完全降順＝終了
        else {
            int ceilIndex = findCeil(str, str[i], i + 1, size - 1);
            swapChar(&str[i], &str[ceilIndex]); // 該当位置を入れ替え
            qsort(str + i + 1, size - i - 1,
                  sizeof(str[0]), compare);     // 右側を再ソート
        }
    }
}

int main() {
    char str[] = "SNGY";
    cout << "All permutations of the string " << str << " are :\n";
    printPermutations(str);
    return 0;
}

実行結果

All permutations of the string SNGY are :
GNSY GNYS GSNY GSYN GYNS GYSN NGSY NGYS NSGY NSYG NYGS NYSG SGNY SGYN SNGY SNYG SYGN SYNG YGNS YGSN YNGS YNSG YSGN YSNG

計算量について

n 文字の文字列の場合、順列の総数は最大 n! 個になるため、全体の計算量は順列の個数に強く依存します。また、各ステップで右側の部分をソートしているため、1回の更新あたり O(n log n) のコストがかかる点にも注意しましょう。

STL を使った簡潔な実装

実際の開発では、C++ 標準ライブラリの std::next_permutation を使うと、同じ処理をはるかに簡潔に記述できます。事前に std::sort で昇順ソートしておけば、重複する順列は自動的にスキップされます。

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string str = "SNGY";
    sort(str.begin(), str.end());
    do {
        cout << str << "\t";
    } while (next_permutation(str.begin(), str.end()));
    return 0;
}

まとめ

重複文字を含む文字列の順列列挙では、「辞書順に次の順列を生成する」アプローチを採用することで、重複を自然に回避できます。競技プログラミングや実務では、std::next_permutation を活用するのが最もシンプルで安全な選択肢と言えるでしょう。