使用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.

有两种方法可以打印给定字符串的所有排列

Rotate()

我们要使用的第一种方法是使用旋转方法。在此方法中，我们将使用 STL 的旋转函数，该函数用于旋转字符串，并且我们将使用递归来打印排列。

示例

上述方法的 C++ 代码

立即学习“C++免费学习笔记（深入）”；

#include
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。

HTTPie AI

AI API开发工具

下载

如您所知，此函数检查下一个排列；因此，我们首先需要按字典顺序对字符串进行排序，以便获得所有可能的排列。

示例

上述方法的 C++ 代码

#include
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函数及其使用。我们希望本教程对您有所帮助。