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

什么是全排列？

在数学中，全排列是指对给定的一组数据（一般为数字或字母组成的序列）进行全排列，即将这些数据进行重新排列，使得每一种排列方式均恰好出现一次。例如，对于给定字符串 “ABC”，它的全排列为 “ABC”、“ACB”、“BAC”、“BCA”、“CAB”、“CBA”。

STL中的函数实现

std::next_permutation

在C++的 STL标准库头文件中，有一个函数叫做 next_permutation，它的实现非常简单，只需要调用该函数即可得到给定字符串的全排列。

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main() 
{
    string s = "ABC";
    sort(s.begin(), s.end());
    do 
    {
        cout << s << endl;
    } while (next_permutation(s.begin(), s.end()));
    return 0;
}

上面的代码中，我们在进入 do while 循环前，用 sort() 排序函数对字符串进行了排序。这是因为 next_permutation 函数只能对排好序的字符串进行全排列。当程序运行时，依次输出了全排列的结果。

std::prev_permutation

除了 next_permutation 外，STL库也提供了另一个函数 prev_permutation，它与 next_permutation 的作用基本一致，不同之处在于 prev_permutation 得到的是给定字符串的前一个全排列。理解了 next_permutation 的实现过程后，我们可以轻易地得出 prev_permutation 的实现方法。

std::permutation

在STL库中，除了上面提到的两种函数外，还有一种名为 permutation 的函数。与前面两种函数不同的是， permutation 函数可以用于返回指定长度的排列，并不限制在字符串上。

以下是该函数的实现：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() 
{
    int arr[] = {1, 2, 3};
    vector v(arr, arr + sizeof(arr) / sizeof(arr[0]));
    sort(v.begin(), v.end());
    do 
    {
        for (int i = 0; i < v.size(); ++i) 
        {
            cout << v[i] << " ";
        }
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));
    return 0;
}

运行程序，依次输出了全排列的结果。

小结

本文介绍了在 C++的 STL库中，如何通过调用相关函数对给定字符串进行全排列、前一个全排列和指定长度排列。通过学习本文内容，相信读者已经掌握了使用 STL库实现全排列的方法。