STLを使用した特定の文字列のC++順列

文字列の順列は、指定された文字列の文字が任意の形式で再配置されたときに形成されます。このチュートリアルでは、たとえば、C++の標準テンプレートライブラリを使用して、特定の文字列のすべての順列を出力する方法について説明します。

Input : s = “ADT”

Output : “ADT”, “ATD”, “DAT”, “DTA”, “TAD”, “TDA”

Explanation : In the given output as you can see all the string are made up of same three character present in our string and are just rearranged thus they fit in the definition of a permutation of a string now there is one more thing to note these are all the permutations possible of string s.

特定の文字列のすべての順列を出力する方法は2つあります

Rotate（）

最初に使用する方法は、rotateメソッドを使用することです。この方法では、文字列を回転させるために使用されるSTLのrotate関数を使用し、順列を出力するために再帰を使用します。

例

上記のメソッドのC++コード

#include<bits/stdc++.h>
using namespace std;
void permutations(string s, string ans){
    if(s.size() == 0) {
// when our string which needs to
//be rotated becomes empty then it means
//that our permutation is stored in ans
        cout << ans << "\n";
        return ;
    }
    for(int i = 0; i < s.size(); i++){
        permutations(s.substr(1), ans + s[0]);
        // we are adding the
        // first character in our ans
        // passing all elements from index 1 in our
        // rotate string for next function.
        rotate(s.begin(), s.begin()+1, s.end());
        //rotating such that our second element becomes first
    }
}
int main(){
    string s = "ADT"; // given string
    permutations(s, "");
    return 0;
}

出力

ADT
ATD
DTA
DAT
TAD
TDA

Next_Permutation

ここで、STLの別の関数を使用します。つまり、名前が示すようにnext_Permutationとして、この関数の戻り方向は、この文字列の次の順列が存在するかどうかです。いいえの場合、falseを返します。

ご存知のように、この関数は次の順列をチェックします。したがって、最初に文字列を辞書式に並べ替えて、可能なすべての順列を取得する必要があります。

例

上記のメソッドのC++コード

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s = "ADT"; // given string
    sort(s.begin(), s.end()); // sorting the string
    do{
        cout << s << "\n"; // printing the permutations
    }while(next_permutation(s.begin(), s.end())); // till next_permutations returns false
    return 0;
}

出力

ADT
ATD
DAT
DTA
TAD
TDA

上記のプログラムでは、文字列を並べ替えてから、next_permutation関数を使用して、可能なすべての順列を出力します。

結論

このチュートリアルでは、C ++のSTLを使用して、指定された文字列のすべての可能な順列を出力します。また、この問題のC ++プログラムと、いくつかの重要なSTL関数とその使用法についても学びました。このチュートリアルがお役に立てば幸いです。