在 C++ 中打印字符串的所有排列
本文将介绍如何在 C++ 中打印给定字符串的所有排列。
使用 std::next_permutation
在 C++ 中打印字符串的所有排列
std:next_permutation
算法修改给定的范围,以便元素的排列按字典顺序升序排列,如果存在这样的排列,则返回一个真正的布尔值。如果字符串字符按降序排序,则该函数可以对 std::string
对象进行操作以生成其排列。我们可以使用 std::sort
算法和 std::greater
函数对象对字符串进行排序,然后调用 next_permutation
直到它返回 false。后者可以使用 do...while
循环实现,该循环将 next_permutation
语句作为条件表达式,并在每个循环中将字符串打印到 cout
流。
#include <iostream>
#include <iterator>
#include <algorithm>
#include <limits>
using std::cout; using std::endl;
using std::string; using std::cin;
void PrintStringPermutations(string &str)
{
std::sort(str.begin(), str.end(), std::greater<>());
do {
cout << str << endl;
} while (std::next_permutation(str.begin(), str.end()));
}
int main() {
string input;
cout << "Enter string to print permutations: ";
cin >> input;
PrintStringPermutations(input);
return EXIT_SUCCESS;
}
输出:
Enter string to print permutations: nel
nle
nel
lne
len
enl
eln
使用 std::prev_permutation
在 C++ 中打印字符串的所有排列
或者,我们可以利用 STL 中的另一种算法 - std::prev_permutation
,该算法以相同的字典顺序生成给定范围的新排列,但在提供序列时存储先前的排列。除了在 while
循环条件中调用 prev_permutation
函数之外,最终的解决方案仍然与前面的示例类似。
#include <iostream>
#include <iterator>
#include <algorithm>
#include <limits>
using std::cout; using std::endl;
using std::string; using std::cin;
void PrintStringPermutations(string &str)
{
std::sort(str.begin(), str.end(), std::greater<>());
do {
cout << str << endl;
} while (std::prev_permutation(str.begin(), str.end()));
}
int main() {
string input;
cout << "Enter string to print permutations: ";
cin >> input;
PrintStringPermutations(input);
return EXIT_SUCCESS;
}
输出:
Enter string to print permutations: nel
nle
nel
lne
len
enl
eln
此外,可以通过实现用户字符串验证功能来确保更健壮的代码,该功能将打印输入提示,直到用户提供有效字符串。请注意,所有列出的解决方案将仅解析来自命令行输入的单个字符串参数,并且不会读取多字字符串。
#include <iostream>
#include <iterator>
#include <algorithm>
#include <limits>
using std::cout; using std::endl;
using std::string; using std::cin;
void PrintStringPermutations(string &str)
{
std::sort(str.begin(), str.end(), std::greater<>());
do {
cout << str << endl;
} while (std::prev_permutation(str.begin(), str.end()));
}
template<typename T>
T &validateInput(T &val)
{
while (true) {
cout << "Enter string to print permutations: ";
if (cin >> val) {
break;
} else {
if (cin.eof())
exit(EXIT_SUCCESS);
cout << "Enter string to print permutations\n";
cin.clear();
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
}
return val;
}
int main() {
string input;
validateInput(input);
PrintStringPermutations(input);
return EXIT_SUCCESS;
}
输出:
Enter string to print permutations: nel
nle
nel
lne
len
enl
eln
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn