C++ 全排列问题——字典序法（permutation函数）

对于输出1 ~ n这些数组成的所有全排列的方法有最暴力的递归枚举法和相对简单写的递归交换法，但是有时我们只希望可以可以找到一个全排列的下一个全排列，就这样出现了字典序法。

例题

洛谷1088 火星人

题目描述
求排列a[1]，a[2]，a[3]，……，a[n]之后的第m个全排列。

输入格式
共三行。
第一行一个正整数N（1 <= N <= 10000）。
第二行一个正整数M（1 <= N <= 100）。
下一行是1到N这N个整数的一个排列，用空格隔开。

输出格式
N个整数，表示第m个全排列。每两个相邻的数中间用一个空格分开。

输入输出样例
输入

5
3
1 2 3 4 5

输出

1 2 4 5 3

全排列问题——字典序法

这里我们要去求一个全排列的下一个全排列，方法步骤如下：

1. 在原排列中从后往前找，找到第一个比它后面数小的数，既找到第一个a[pos]满足a[pos] < a[pos + 1]，简而言之就是找到原排列的最长单调递减的后缀的前一个树。
2. 在原排列的最长单调递减的后缀中从前往后找到最后一个大于a[pos]的数a[k]。
3. 调换a[pos]和a[k]。
4. 对a[pos+1]……a[n]进行转置，此时的排列就是原排列的下一个排列。

这里举个例子：如排列986375421，我们发现原排列的最长单调递减的后缀是75421，而75421前面的第一个数就是3，而这个数3也就是我们再找的a[pos]。之后在排列75421中从前往后找到最后一个大于3的数，既是4，这里我们可以用到二分查找upper_bound函数找到第一个小于3的数的位置，之后将位置减一就是k了。接着调换3和4，序列变为986475321，最后再将75321转置成12357，则我们就求出了排列986375421的下一个全排列为986412357。

还有，记得加一个特判：如果说当前排列整体就是单调递减的，那么这也就是最后一个排列了，直接跳出就ok了，既pos = 0时返回false。

最后算一下算法时间复杂度：先说求一个排列的下一个排列的时间复杂度，我们可以看到是O(n)级别的。而这里要变换m次，所以总时间复杂度是O(n * m)级别的。

代码

# include <cstdio>
# include <cmath>
# include <cstring>
# include <algorithm>

using namespace std;

const int N_MAX = 10000;

int n, m;
int a[N_MAX + 10];

bool cmp(int x, int y)
{
    return x > y;
}

bool permutation()
{
    int pos = n - 1;
    while (pos > 0 && a[pos] > a[pos + 1]) pos--;
    if (pos == 0) return false;
    int k = upper_bound(a + pos + 1, a + n + 1, a[pos], cmp) - a - 1;
    swap(a[pos], a[k]);
    for (int i = pos + 1; i <= (n + pos) / 2; i++)
        swap(a[i], a[n + pos + 1 - i]);
    return true;
}

int main()
{
    scanf("%d", &n);
    scanf("%d", &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++)
        permutation();
    for (int i = 1; i <= n; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

permutation函数

所在头文件：algorithm

next_permutation(a + begin, a + end + 1, cmp);
prev_permutation(a + begin, a + end + 1, cmp);

功能：next_permutation是找到数组a从a[begin]开始到a[end]的后一个全排列，并赋值给a[begin]到a[end]。而prev_permutation就是找到上一个全排列。

返回值：如果还存在下一个（上一个）排列，就返回true。如果a是最后一个排列，返回false。

参数：

1. 首地址（a + begin） 必要
2. 末地址（a + end） 必要
3. 比较函数表示序列如何有序（多数情况下适用于对结构体的搜索） 选要

这样本题就可以拿permutation函数一遍过了（不过推荐各位还是先手写一下字典序法求全排列，之后再试一试permutation函数一遍过）

# include <cstdio>
# include <cmath>
# include <cstring>
# include <algorithm>

using namespace std;

const int N_MAX = 10000;

int n, m;
int a[N_MAX + 10];

int main()
{
    scanf("%d", &n);
    scanf("%d", &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++)
        next_permutation(a + 1, a + n + 1);
    // 如果要倒着找全排列，只要将next_permutation改成prev_permutation就行了 
    for (int i = 1; i <= n; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

C++ 全排列问题——字典序法（permutation函数）

原文：https://www.cnblogs.com/000zwx000/p/12340524.html