【C++】文字列のすべての順列を辞書式順序（ソート順）で出力する方法

問題概要

この問題では、長さ n の文字列が与えられ、その文字を並べ替えてできるすべての順列を、ソートされた順序（辞書式順序）で出力することが求められます。

具体例を使って問題を確認してみましょう。

入力： 「XYZ」

出力： XYZ、XZY、YXZ、YZX、ZXY、ZYX

つまり、すべての順列を辞書式順序（アルファベット昇順）で列挙して出力する必要があります。

解決のアプローチ

この問題を解くための基本的な手順は以下の通りです。

1. まず文字列全体をアルファベット昇順にソートします。ソート後の文字列が順列の最初の要素になります。
2. 現在の順列から「次に大きい順列」を繰り返し生成していきます。

「次の順列」を求める処理は、次のような流れで行われます。

• 右端から走査し、直後の文字より小さい文字（ピボット）を探します。
• ピボットより右側の文字の中から、ピボットより大きい最小の文字を見つけて交換します。
• 交換後、ピボット以降の部分を再び昇順にソートします。
• 文字列全体が降順になった時点ですべての順列の生成が完了したことになります。

以下のコードを見ると、この解法がより明確に理解できるでしょう。

サンプルコード

#include<iostream>
#include<string.h>
using namespace std;
int compare(const void *a, const void * b){
    return ( *(char *)a - *(char *)b );
}
void swap(char* a, char* b) {
    char t = *a;
    *a = *b;
    *b = t;
}
int finduBound(char str[], char first, int l, int h) {
    int ubound = l;
    for (int i = l+1; i <= h; i++)
        if (str[i] > first && str[i] < str[ubound])
            ubound = i;
    return ubound;
}
void generatePermutaion ( char str[] ) {
    int size = strlen(str);
    qsort( str, size, sizeof( str[0] ), compare );
    bool isFinished = false;
    while ( ! isFinished ) {
        cout<<str<<"\t";
        int i;
        for ( i = size - 2; i >= 0; --i )
            if (str[i] < str[i+1])
                break;
        if ( i == -1 )
            isFinished = true;
        else {
            int ubound = finduBound( str, str[i], i + 1, size - 1 );
            swap( &str[i], &str[ubound] );
            qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare );
        }
    }
}
int main() {
    char str[] = "NOPQ";
    cout<<"Permutation in Sorted order :\n";
    generatePermutaion(str);
    return 0;
}

実行結果

Permutation in Sorted order :
NOPQ NOQP NPOQ NPQO NQOP NQPO
ONPQ ONQP OPNQ OPQN OQNP
OQPN PNOQ PNQO PONQ POQN
PQNO PQON QNOP QNPO QONP
QOPN QPNO QPON

まとめ

この手法では、初期ソートによって必ず辞書式順序で最小の順列から開始でき、その後は「次の順列」を順番に生成していくため、すべての順列が自然に辞書式順序で出力されます。計算量は順列の総数（n!）に依存しますが、重複する文字がない限り各順列を1回ずつ効率的に列挙できます。