使用STL实现给定字符串的C++全排列-C++-php.cn

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

Salin selepas log masuk

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

Rotate()

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

示例

上述方法的 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; }

Salin selepas log masuk

输出

ADT ATD DTA DAT TAD TDA

Salin selepas log masuk

Next_Permutation

现在我们将使用STL的另一个函数，即next_Permutation，顾名思义，该函数的返回值是该字符串的下一个排列是否存在。如果不是，则返回 false。

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

示例

上述方法的 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; }

Salin selepas log masuk