算法：全排里问题——邻位互换法

邻位互换法，只要你在学全排列就不可不学的一个及其有趣的算法。

例题

洛谷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. 初始化全排列1, 2, 3，…… ，n。
2. 将指针都指向左侧，即face[i] = -1。
3. 从a[1] ~ a[n]中找出处于活动状态的最大值的位置pos。
4. 如果没有一个处于活动状态的数，代表所有的全排列已经生成完毕。
5. 交换a[pos]和其指向的数a[pos_to]。pos_to就是a[pos]指向的位置，即pos + face[pos]。
6. 交换face[pos]和face[pos_to]。这步千万不要忘！
7. 在排列中将所有的大于a[pos_to]的数的face都取反。这里一定时a[pos_to]因为我们已经交换了a[pos]和a[pos_to]。
8. 不停地循环重复步骤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("
");
	} while (permutation());
	return 0;
}