迹忆客 专注技术分享

本文将介绍如何在 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