全排列——邻位对换法

1、全排列邻位对换法(算法)全排列邻位对换法一个能够快速生成全排列的算法叫做邻位对换法，它之所以 较快，是因为邻位对换法中下一个排列总是上一个排列某相 邻两位对换得到的，只需一步，就可以得到一个新的全排列， 而且绝不重复，但是由于每将 n 从一端移动到另一端后，就 需要遍历排列2次，来寻找最大的可移数 m，所以速度得到 了限制。它的原理是：n的全排列可由n-1的全排列生成：给定n-1的一个排列n , 将n由最右端依次插入排列n，即得到n个n的排列：P1 P2 P(n-1) nP1 P2 n P(n-1)n P1 P2 P(n-1)对上述过程，一般地，对i，将前一步所得的每一排列重复i次，然后将 i

2、 由第一排的最后往前移，至最前列，正好走了 i 次,下一个接着将 i 放在下一排列的最前面，然后依次往后 移，一直下去即得 i 元排列。考虑1,2 - n的一个排列，其上每一个整数都给了一个方向，如果它的箭头所指的方向的邻点小于它本身，我们称整数 是可移的。显然 1 永远不可移， n 除了以下两种情形外，它都是可移的(1) n 是第一个数，且其方向指向左侧(2) n 是最后一个数，且其方向指向右侧 于是，我们可按如下算法产生所有排列：1，开始时：存在排列 123n,除1夕卜，所有元素均可移， 即方向都指向左侧。2，当最大元素 n 可移动时， 将其从一端依次移动到另一端， 即可得到 n-1 个全

3、排列；当 n 移动到某一端后， 不能再移动， 此时寻找最大的可移数 m，将m与其箭头所指的邻数 (这个 数当然不会是N，否则怎么可移) 互换位置，这样就又得到一个新的全排列；将所得新排列中 所有比 m 大的数 p 的方向调整， 即改为相反方向， 这样使得 n 又成了可移数。3，重复第 2 步直到所有的元素都不能移动为止。以 4 个元素的排列为例，首先生成全排列 1 2 3 4 ； 找到最大的可移数 4，将 4 与其箭头所指的邻数互换位置， 可以生成 3 个新排列：1 2 4 31 4 2 3因为没有比4更大的数p，所以无需调整p的方向。最大数4 到了最左边后， 由于其方向指向左侧， 所以 4

4、不能再移动。 接下来寻找最大的可移数 3，将 3与其箭头所指的邻数 2 互 换位置，可以得到新排列： 4 1 3 2 ；然后将所得排列中比 3大的数 4的方向调整， 使得 4可以移 动，重新成为最大的可移数，将 4 与其箭头所指的邻数互换 位置，可以生成 3 个新排列：1 4 3 21 3 4 21 3 2 4此时最大数 4 到了最右边，又因为其方向指向右侧，所以 4 不能再移动；于是我们寻找最大的可移数 3，将 3 与其箭头 所指的邻数 1互换位置，可以得到新排列： 3 1 2 4 ； 然后将所得排列中比 3大的数 4的方向调整， 使得 4可以移 动，重新成为最大的可移数，将 4 与其箭头所

5、指的邻数互换 位置，可以生成 3 个新排列：3 1 4 23 4 1 24 3 1 2 如此循环，直到所有的数都不能移动，即可求出全部排列。 最后得到的一个全排列为： 2 1 3 4 ，此时 2 指向左侧， 1， 3，4 均指向右侧。根据上述算法分析，使用一个辅助数组来存储各个元素的指向，我们可以得到代码如下：/*函数名称： Permutation 函数功能：排列邻位对换法：输出 n 个数的所有全排列 输入变量： int n ： 1， 2，3， .，n 共 n 个自然数 输出变量：无*/void Permutation(int n)int *a = new intn; / 用来存储 n 个自然

6、数bool *p = new booln; / 用来存储 n 个元素的指向：向左 为 false ，向右为 truefor (int i=0; i<n; i+) / 存储全排列的元素值，并计算全 排列的数量ai = i + 1;pi = false; / 开始均指向左侧doPrint(a, n); / 输出第一个全排列if (n = an-1)/ 若 n 在最右侧， 将其逐次与左侧的元素交 换，得到 n - 1 个新的排列for (int i=n-1; i>0; i-)int temp = ai; ai = ai-1; ai-1 = temp;bool flag = pi; pi

7、= pi-1; pi-1 = flag;Print(a, n);else / 若 n 在最左侧，将其逐次与右侧的元素交换， 得到 n - 1 个新的排列for (int i=1; i<n; i+)int temp = ai; ai = ai-1; ai-1 = temp;bool flag = pi; pi = pi-1; pi-1 = flag;Print(a, n); while (Move(a, p, n);delete a; delete p;/*函数名称： Move函数功能： 寻找最大可移数， 可移数 m ，将 m 与其箭头所指 的邻数互换位置，并将所得新排列中所有比 m 大的

8、数 p 的方向调整 输入变量： int a ：存储了 1，2，3， .， n 共 n 个自然数的 数组bool p ：存储了 n 个元素的指向的数组：向左为 false ， 向右为 trueint n ：数组 a 的长度 输出变量：排列中存在最大可移数，则做了相关操作后返回 真，否则直接返回假*/bool Move(int a, bool p, int n)int max = 1; int pos = -1;for (int i=0; i<n; i+)if (ai < max)continue;if (pi && i < n-1 && ai &

9、gt; ai+1) | / 指向右侧(!pi && i > 0 && ai > ai-1) /指向左侧max = ai;pos = i;if (pos = -1) / 都不能移动return false;/与其箭头所指的邻数互换位置if (ppos) / 指向右侧int temp = apos; apos = apos+1; apos+1 = temp; bool flag = ppos; ppos = ppos+1; ppos+1 = flag;else / 指向左侧int temp = apos; apos = apos-1; apos-1 = te