算法:全排列问题——字典序法

求一个排列的下一个排列我们有暴力的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("
");
	return 0;
}
原文地址:https://www.cnblogs.com/000zwx000/p/12340524.html