C++のSTLを活用して文字列のすべての順列を生成する方法

はじめに

文字列の順列（パーミュテーション）とは、与えられた文字列の文字をさまざまな順序に並べ替えてできる文字列のことです。このチュートリアルでは、C++の標準テンプレートライブラリ（STL）を使用して、指定された文字列のすべての順列を出力する方法を解説します。

具体例

入力 : s = "ADT"

出力 : "ADT", "ATD", "DAT", "DTA", "TAD", "TDA"

説明 : 出力を見ると、すべての文字列が元の文字列に含まれる同じ3文字で構成され、単に並べ替えられているだけであることがわかります。したがって、これらは文字列の順列の定義に合致します。また重要な点として、これらは文字列sから作れるすべての順列です。

指定された文字列のすべての順列を出力するには、大きく分けて2つの方法があります。

方法1：rotate()関数を使う

最初の方法は、STLのrotate関数を利用するものです。rotate関数は文字列を回転させる機能を持っており、これを再帰処理と組み合わせることで、すべての順列を効率よく出力できます。

C++コード例

#include<bits/stdc++.h>
using namespace std;
void permutations(string s, string ans){
    if(s.size() == 0) {
// 回転対象の文字列が空になったら、
// 順列がansに格納されていることを意味する
        cout << ans << "\n";
        return ;
    }
    for(int i = 0; i < s.size(); i++){
        permutations(s.substr(1), ans + s[0]);
        // 先頭の文字をansに追加し、
        // インデックス1以降の要素を次の呼び出しに渡す
        rotate(s.begin(), s.begin()+1, s.end());
        // 2番目の要素が先頭に来るように回転させる
    }
}
int main(){
    string s = "ADT"; // 対象の文字列
    permutations(s, "");
    return 0;
}

実行結果

ADT
ATD
DTA
DAT
TAD
TDA

このプログラムでは、各再帰呼び出しのたびに文字列を回転させることで、異なる文字を先頭に持ちながら順列を構築していきます。文字列が空になった時点で、完成した順列が出力されます。

方法2：next_permutation()関数を使う

次に、STLのもう一つの便利な関数であるnext_permutationを紹介します。その名の通り、この関数は「次の順列」が存在するかどうかを判定し、存在しない場合はfalseを返します。

この関数は辞書式順序で次の順列を生成する仕組みのため、すべての可能な順列を漏れなく取得するには、あらかじめ文字列をsort関数で辞書式順序にソートしておく必要があります。

C++コード例

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s = "ADT"; // 対象の文字列
    sort(s.begin(), s.end()); // 文字列をソート
    do{
        cout << s << "\n"; // 順列を出力
    }while(next_permutation(s.begin(), s.end())); // next_permutationがfalseを返すまで繰り返す
    return 0;
}

実行結果

ADT
ATD
DAT
DTA
TAD
TDA

上記のプログラムでは、まず文字列をソートし、その後next_permutation関数をdo-whileループで繰り返し呼び出すことで、すべての可能な順列を順番に出力しています。コードが簡潔になり、可読性も高まるのがこの方法の利点です。

まとめ

このチュートリアルでは、C++のSTLを活用して、指定された文字列のすべての順列を出力する2つの方法を学びました。rotate関数と再帰を組み合わせる方法と、next_permutation関数を使う方法のどちらも実務で役立つテクニックです。特にnext_permutation関数は、ソートと組み合わせるだけで簡単に全順列を列挙できるため、競技プログラミングなどでも頻繁に使用されます。ぜひ実際にコードを実行して、動作を確認してみてください。