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

本文主要是介绍算法：全排列问题——邻位互换法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

例题

洛谷1706 全排列问题

题目描述
按照邻位互换法的顺序输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式
一个整数n。

输出格式
由1～n组成的所有不重复的数字序列，每行一个序列。
每个数字保留 5个场宽。

输入样例

3

输出样例

    1    2    31    3    22    1    32    3    13    1    23    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!)。

代码

# i

这篇关于算法：全排列问题——邻位互换法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---