STL 全排列函数详解

头文件 #include <algorithm>

next_permutation：求下一个排列组合　

函数模板：next_permutation(arr, arr+size);
参数说明：
　　arr：数组名
　　size：数组元素个数
函数功能：返回值为bool类型，当当前序列不存在下一个排列时，函数返回false，否则返回true，排列好的数在数组中存储
.注意：在使用前需要对欲排列数组按升序排序，否则只能找出该序列之后的全排列数。比如，如果数组num初始化为2,3,1，那么输出就变为了：{2 3 1} {3 1 2} {3 2 1}

prev_permutation：求上一个排列组合

函数模板：prev_permutation(arr, arr+size);
参数说明：
　　arr：数组名
　　size：数组元素个数
函数功能：返回值为bool类型，当当前序列不存在上一个排列时，函数返回false，否则返回true]
注意：在使用前需要对欲排列数组按降序排序，否则只能找出该序列之后的全排列数。

对string类型：

string s;
while (getline(cin, s)) {
    sort(s.begin(), s.end());
    do
    {
        cout << s << endl;
    } while (next_permutation(s.begin(), s.end()));
    cout << endl;
}

对数组类型：

for (int i = 0; i < n; i++)cin >> a[i];
sort(a, a + n);
do
{
    for (int i = 0; i < n; i++)cout << a[i];
    cout << endl;
} while (next_permutation(a, a + n));
cout << endl;

递归求全排列

比如这里所说的全排列{"a","b","c","d"};

1。首先四个字母的全排列可以被简化成分别以"a"、"b"、"c"、"d"打头，加上剩下三个字母的全排列；

2。以此类推，上一步中的每一个三个字母的全排列，又可以被简化为分别以三个字母打头，加上剩下两个字母的全排列

3。重复前面的简化过程，直到只剩一个字母的时候，就很容易了处理了，因为一个字母的全排列太显而易见了

void pailie(string &str, int s, int t) {
    if (s == t) { cout << str << endl; return; }
    for (int i = s; i <= t; i++) {
        swap(str[s], str[i]);
        pailie(str, s + 1, t);//将str[s:t]的全排列转化为以s[i]开头 s[s+1:t]的全排列
        swap(str[s], str[i]);
    }
}