邻位互换法,只要你在学全排列就不可不学的一个及其有趣的算法。
例题
洛谷1706 全排列问题
题目描述
按照邻位互换法的顺序输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数n。
输出格式
由1~n组成的所有不重复的数字序列,每行一个序列。
每个数字保留 5个场宽。
输入样例
3
输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
全排列问题——邻位互换法
邻位互换法其实是一个比较容易理解的算法,这里我们需要定义一个概念:如果说一个数比它指针所指向的数小,它就处于活动状态,当然所指向的数不能越界。此时,你可能会问这个指针是啥,其实这个指针只能指向他的下一个数或者上一个数,比如a[i]的指针只能指向a[i - 1]或者a[i + 1]。这个指针我们就用face[i]来记录:当face[i] = 1时,表示a[i]指向a[i + 1];当face[i] = -1时,表示a[i]指向a[i - 1]。这样使用起来也很方便,比如我要去找a[i]的指向位置,直接就是a[i + face[i]],不用再去if判断了。
引入这个概念之后,我们就具体来说步骤了:
- 初始化全排列1, 2, 3,…… ,n。
- 将指针都指向左侧,即face[i] = -1。
- 从a[1] ~ a[n]中找出处于活动状态的最大值的位置pos。
- 如果没有一个处于活动状态的数,代表所有的全排列已经生成完毕。
- 交换a[pos]和其指向的数a[pos_to]。pos_to就是a[pos]指向的位置,即pos + face[pos]。
- 交换face[pos]和face[pos_to]。这步千万不要忘!
- 在排列中将所有的大于a[pos_to]的数的face都取反。这里一定时a[pos_to]因为我们已经交换了a[pos]和a[pos_to]。
- 不停地循环重复步骤3、4、5、6、7,每次执行完一次就进行输出,直到4步骤返回false,结束。
最后,算一下算法的时间复杂度:每次求下一个排列仅n次即可,共有n!的全排列,所以总时间复杂度为O(n * n!)。
代码
# include <cstdio>
# include <algorithm>
# include <cstring>
# include <cmath>
using namespace std;
const int N_MAX = 10;
int n;
int a[N_MAX + 10];
int face[N_MAX + 10];
bool canMove(int x)
{
int y = x + face[x];
return y >= 1 && y <= n && a[x] > a[y];
}
bool permutation()
{
int a_max = 0, pos = -1;
for (int i = 1; i <= n; i++) {
if (!canMove(i) || a_max > a[i]) continue;
a_max = a[i], pos = i;
}
if (pos == -1) return false;
int pos_to = pos + face[pos];
swap(a[pos], a[pos_to]);
swap(face[pos], face[pos_to]);
for (int i = 1; i <= n; i++)
if (a[i] > a_max) face[i] = -face[i];
return true;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
a[i] = i;
memset(face, -1, sizeof(face));
do {
for (int i = 1; i <= n; i++)
printf("%5d", a[i]);
printf("\n");
} while (permutation());
return 0;
}