邻位对换法是全排列生成算法中的其中一种，它的换位是双向的，通过保存数字的“方向性”来快速得到下一个排列。

设我们要生成n=9的全排列（1,2,3,4,5,6,7,8,9），设定b2b3b4b5b6b7b8b9为我们要求的中介数。

2的方向一定是向左。b2就是从2开始,背向2的方向所有比2小的数字的个数。知道了b2的值之后就可以推 导出b3b4……直到b9的值。

规则如下：

对于每一个大于2的数字i，

如果i为奇数，其方向性决定于bi-1的奇偶性，奇向右、偶向左。

如果i为偶数，其方向性决定于bi-1+ bi-2的奇偶性，同样是奇向右、偶向左。

当得到方向性后，bi的值就是背向i的方向直到排列边界这个区间里比i小的数字的个数。如此就能得到邻位对 换法的中介数。

举例

原排列（839647521）生成中介数方法：

如右图1所示，

2的方向向左，

背向2的方向中比2小的数字有1个，b2=1

3的方向由b2为奇可以断定向右，

背向3的方向中比3小的数字有0个，b3=0

4的方向由b2+b3为奇可以断定向右，

背向4的方向中比4小的数字有1个，b4=1

5的方向由b4为奇可以断定向右，

背向5的方向中比5小的数字有2个，b5=2

6的方向由b4+b5为奇可以断定向右，

背向6的方向中比6小的数字有1个，b6=1

7的方向由b6为奇可以断定向右，

背向7的方向中比7小的数字有3个，b7=3

8的方向由b6+b7为偶可以断定向左，

背向8的方向中比8小的数字有7个，b8=7

9的方向由b8为奇可以断定向右，

背向9的方向中比9小的数字有2个，b9=2

从中介数(10121372)得到原排列:

9：b8=7奇→9向右b9=2向右第3个空，

8：b6+b7=1+3=4偶→8向左b8=7 向左第8个空

7：b6=1奇→7向右，b7=3 向右第4个空

6：b4+b5=1+2=3奇→6向右，b6=1,向右第2个空

5：b4=1奇→5向右，b5=2,向右第3个空

4：b2+b3=1奇→4向右, b4=1,向右第2个空

3：b2=1奇→3向右， b3=0,向右第1个空

2：b2=1,向左第2个空

总之，如若要从原排列生成下一个排列，首先将原排列按上述方法转换为中介数，再将中介数加一，得到新中介数，再将新中介数用以上方法换算为下一个排列。

一、算法的原理：

{1, 2, 3, …, n-1, n}的全排列可由{1, 2, 3, …, n-1}的全排列得出。具体做法为针对{1, 2, 3, …, n-1}的任意一个排列{a1, a2, a3, …, an-1}，将n插入n个不同的位置得到：

{a1, a2, a3, …, an-1, n},

{a1, a2, a3, …, n, an-1},

……

{a1, a2, n, …, an-2, an-1},

{a1, n, a2, …, an-2, an-1},

{n, a1, a2, …, an-2, an-1}

即可得到{1, 2, 3, …, n-1, n}的全排列。

二、邻位对换法：

1、 每个数有一个移动方向，向左或向右。如果数x的移动方向上最靠近它的数比它要小，那么x是可移动的。初始时序列为{1, 2, 3, …, n-1, n}，方向都为向左。

2、 移动最大数n，直到不能移动为止，每改变一次位置输出一个序列（此时n在最左边或最右边）。

3、 找当前可移动的最大数m。若能找到，移动m，把所有比m大的数的方向置反，返回第2步；若不能找到，算法停止。

举例：

用sign[]来表示方向，sign[i]表示第i+1大的数的方向。用perm[]来表示序列，以n=4为例。

1、初始状态

sign:{0, 0, 0, 0}

perm:{1, 2, 3, 4}

移动n=4

perm:{1, 2, 4, 3}

perm:{1, 4, 2, 3}

perm:{4, 1, 2, 3} //能注意到，这4个是在{1, 2, 3}的基础上添加4得到的排列

2、找到可移动的最大数m=3，移动m，把4的方向置反

sign:{0, 0, 0, 1}

perm:{4, 1, 3, 2}

移动n=4

perm:{1, 4, 3, 2}

perm:{1, 3, 4, 2}

perm:{1, 3, 2, 4} //能注意到，这4个是在{1, 3, 2}的基础上添加4得到的排列

3、找到可移动的最大数m=3，移动m，把4的方向置反

sign:{0, 0, 0, 0}

perm:{3, 1, 2, 4}

移动n=4

perm:{3, 1, 4, 2}

perm:{3, 4, 1, 2}

perm:{4, 3, 1, 2} //能注意到，这4个是在{3, 1, 2}的基础上添加4得到的排列

4、 找到可移动的最大数m=2，移动m，把3, 4的方向置反

sign:{0, 0, 1, 1}

perm:{4, 3, 2, 1}

移动n=4

perm:{3, 4, 2, 1}

perm:{3, 2, 4, 1}

perm:{3, 2, 1, 4} //能注意到，这4个是在{3, 2, 1}的基础上添加4得到的排列

5、 找到可移动的最大数m=3，移动m，把4的方向置反

sign:{0, 0, 1, 0}

perm:{2, 3, 1, 4}

移动n=4

perm:{2, 3, 4, 1}

perm:{2, 4, 3, 1}

perm:{4, 2, 3, 1} //能注意到，这4个是在{2, 3, 1}的基础上添加4得到的排列

6、 找到可移动的最大数m=3，移动m，把4的方向置反

sign:{0, 0, 1, 1}

perm: {4, 2, 1, 3}

移动n=4

perm: {2, 4, 1, 3}

perm: {2, 1, 4, 3}

perm: {2, 1, 3, 4} //能注意到，这4个是在{2, 1, 3}的基础上添加4得到的排列

此时发现没有可移动的数了，算法结束。

三、c语言实现示例：

#include

#define MAXSIZE 100

int orientation[MAXSIZE];

char permData[MAXSIZE];

long count = 0;

void generatePearm(int n) {

int pos;

char temp;

if (permData[0] == ('a' + n - 1)) {

pos = 0;

while(pos < n - 1) {

count++;

//puts(permData);

temp = permData[pos];

permData[pos] = permData[pos+1];

permData[pos+1] = temp;

pos++;

}

count++;

//puts(permData);

} else {

pos = n - 1;

while (pos > 0) {

count++;

//puts(permData);

temp = permData[pos];

permData[pos] = permData[pos-1];

permData[pos-1] = temp;

pos--;

}

count++;

//puts(permData);

}

}

int nCantMove(int n) {

char max = 'a';

int pos = -1, i;

for (i = 1; i < n - 1; i++) {

if (permData[i] < max)

continue;

if ((orientation[permData[i]-'a'] && permData[i] > permData[i+1]) || (!orientation[permData[i]-'a'] && permData[i] > permData[i-1])) {

max = permData[i];

pos = i;

}

}

if ((permData[0] != 'a' + n - 1) && permData[0] > max && permData[0] > permData[1] && orientation[permData[0]-'a']) {

max = permData[0];

pos = 0;

}

if ((permData[n-1] != 'a' + n - 1) && permData[n-1] > max && permData[n-1] > permData[n-2] && !orientation[permData[n-1]-'a']) {

max = permData[n-1];

pos = n - 1;

}

if (max == 'a')

return 0;

if (orientation[max-'a']) {

permData[pos] = permData[pos+1];

permData[pos+1] = max;

} else {

permData[pos] = permData[pos-1];

permData[pos-1] = max;

}

for (i = 0; i < n; i++) {

if (permData[i] > max) {

orientation[permData[i]-'a'] = 1 - orientation[permData[i]-'a'];

}

}

return 1;

}

void nearPosExchGeneratePerm(int n) {

do {

generatePearm(n);

} while (nCantMove(n));

}

int main() {

int n, i;

for (i = 0; i < n; i++) {

orientation[i] = 0;

permData[i] = 'a' + i;

}

nearPosExchGeneratePerm(n);

return 0;

}