C++で文字列の辞書式順序における次の順列を生成する方法

本記事では、C++を使って文字列の辞書式順序における次の順列を生成する方法を解説します。

辞書式順序の次の順列とは？

辞書式順序における「次の順列」とは、現在の順列よりも辞書式に大きい順列の中で、最も小さいものを指します。たとえば、「ACB」の次の順列は「BAC」です。

ただし、すべての文字列に次の順列が存在するわけではありません。たとえば「BBB」や「DCBA」のように、すでに降順に並んでいる（それ以上大きい並び替えが存在しない）場合には、次の順列はありません。

next_permutation() 関数を使う

C++では、<algorithm>ヘッダーに用意されている next_permutation() 関数を使用することで、この処理を簡単に実装できます。

この関数は、指定した範囲の要素をその場で（in-placeで）次の順列に並べ替えます。戻り値としては、次の順列が存在すれば true を、存在しなければ false を返します。なお、次の順列が存在しない場合は、範囲が昇順（最初の順列）に並べ替えられる点にも注意してください。

サンプルコード

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

int main() {
    string s = "DBAC";
    for(int i = 0; i < 5; i++) {
        bool val = next_permutation(s.begin(), s.end());
        if (val == false) {
            cout << "No next permutation" << endl;
            break;
        } else
            cout << "Next: " << s << endl;
    }
}

実行結果

Next: DBCA
Next: DCAB
Next: DCBA
No next permutation

コードの解説

このプログラムでは、初期値として「DBAC」という文字列を用意し、ループ内で next_permutation() を繰り返し呼び出しています。

• 1回目：「DBAC」→「DBCA」（Dを固定し、BACの部分を並べ替え）
• 2回目：「DBCA」→「DCAB」
• 3回目：「DCAB」→「DCBA」
• 4回目：「DCBA」は完全な降順のため、次の順列が存在せず false が返され、メッセージを表示してループを終了します。

このように、next_permutation() を活用すれば、自前で複雑なアルゴリズムを実装することなく、順列の全列挙や次の順列の取得を簡潔なコードで実現できます。競技プログラミングや組み合わせ問題の求解などでも頻繁に活用される便利な関数です。