首页> 后端开发> C++> 正文

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

王林
发布: 2023-09-01 23:33:06
转载
813 人浏览过

使用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++ 代码

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

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

示例

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

以上是使用STL实现给定字符串的C++全排列的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!