算法:全排列问题——字典中介法

有时我们希望可以找到一个全排列的下m个全排列,而不仅仅是下一个,就这样出现了字典中介法。

例题

洛谷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

全排列问题——字典中介法

这里对于一个全排列我们需要一个中介数,举个例子假设我们要求839647521的下100个全排列,这里我们生成其对应的中介数:8后面比8小的有7个数,3后面比3小的有2个数,9后面比9小的有6个数,6后面比6小的有4个数……mid[i]表示a[i]后面比a[i]小的数的个数,得到中介数mid = 726423210。

我们可以发现对于mid[i]最大为(n - i),因为位置i后面有(n - i)个位置,只有当后面所有数都比它小的时候mid[i] = (n - i)。这样我们就可以发现中介数mid除去最后一个0就是一个递增进位制数(第i位的进位制是(n - i + 1),最后一位是二进制,因为一进制恒为0),这样我们让这个递增进位制数72642321加上100,就是72652011

递增进位制(72642321) + 十进制(100)

  • 倒数第一位是1 + 100 = 101,进位制是2,所以向下一位进50,mid[n - 1] = 1。
  • 倒数第二位是2 + 50 = 52,进位制是3,所以向下一位进17,mid[n - 2] = 1。
  • 倒数第三位是3 + 17 = 20,进位制是4,所以向下一位进5,mid[n - 3] = 0。
  • 倒数第四位是2 + 5 = 7,进位制是5,所以向下一位进1,mid[n - 4] = 2。
  • 倒数第五位是4 + 1 = 5,进位制是6,所以不再进位,mid[n - 5] = 5。

最后得到递增进位制(72652011),这也就是下100个排列的中介数了。

这里要加个特判:如果mid[0]大于0了,代表这个排列比排列n,(n - 1),……,1还大,那么根本没有这种排列,所以直接返回false就行了。

用递增进位制数再求出排列:中介数mid[i]表示第i位右侧比a[i]小的数的个数,因此我们每次从1开始数(mid[i] + 1)个,这里选过的数字不能再算在其中,那么数到的这个数字就是a[i]的值,下面是例子。
在这里插入图片描述
最后算一下算法时间复杂度:最多的有两重循环,所以时间复杂度是O(n^2)。

代码

# 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 mid[N_MAX + 10]; // mid[i]表示排列中第i位后面比a[i]小的数的个数
bool flag[N_MAX + 10]; // flag[i]表示新排列中数字i是否被使用 

bool permutation()
{
	for (int i = 1; i <= n - 1; i++)
		for (int j = i + 1; j <= n; j++)
			mid[i] += (a[i] > a[j]);
	mid[n - 1] += m;
	for (int i = n - 1; i > 0 && mid[i] >= n - i + 1; i--) {
		mid[i - 1] += mid[i] / (n - i + 1); 
		mid[i] %= n - i + 1;
	}
	if (mid[0] > 0) return false;
	for (int i = 1; i <= n; i++) {
		int pos = 1;
		for (int j = 0; pos <= n; pos++) {
			j += !flag[pos];
			if (j > mid[i]) break;
		}
		flag[pos] = true;
		a[i] = pos;
	}
	return true;
}

int main()
{
	scanf("%d", &n);
	scanf("%d", &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	permutation();
	for (int i = 1; i <= n; i++)
		printf("%d ", a[i]);
	printf("
");
	return 0;
}
原文地址:https://www.cnblogs.com/000zwx000/p/12360302.html