搜索

邻位对换法

全排列生成算法中的其中一种

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

规则
设我们要生成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;
}
全国各地天气预报查询

上海市

  • 市辖区

    • 云南省

  • 临沧市

    • 云南省

  • 丽江市

    • 云南省

  • 保山市

    • 云南省

  • 大理白族自治州

    • 云南省

  • 德宏傣族景颇族自治州

    • 云南省

  • 怒江傈僳族自治州

    • 云南省

  • 文山壮族苗族自治州

    • 云南省

  • 昆明市

    • 云南省

  • 昭通市

    • 云南省

  • 普洱市

    • 云南省

  • 曲靖市

    • 云南省

  • 楚雄彝族自治州

    • 云南省

  • 玉溪市

    • 云南省

  • 红河哈尼族彝族自治州

    • 云南省

  • 西双版纳傣族自治州

    • 云南省

  • 迪庆藏族自治州

    • 内蒙古自治区

  • 乌兰察布市

    • 内蒙古自治区

  • 乌海市

    • 内蒙古自治区

  • 兴安盟

    • 内蒙古自治区

  • 包头市

    • 内蒙古自治区

  • 呼伦贝尔市

    • 内蒙古自治区

  • 呼和浩特市

    • 内蒙古自治区

  • 巴彦淖尔市

    • 内蒙古自治区

  • 赤峰市

    • 内蒙古自治区

  • 通辽市

    • 内蒙古自治区

  • 鄂尔多斯市

    • 内蒙古自治区

  • 锡林郭勒盟

    • 内蒙古自治区

  • 阿拉善盟

    • 北京市

  • 市辖区

    • 吉林省

  • 吉林市

    • 吉林省

  • 四平市

    • 吉林省

  • 延边朝鲜族自治州

    • 吉林省

  • 松原市

    • 吉林省

  • 白城市

    • 吉林省

  • 白山市

    • 吉林省

  • 辽源市

    • 吉林省

  • 通化市

    • 吉林省

  • 长春市

    • 四川省

  • 乐山市

    • 四川省

  • 内江市

    • 四川省

  • 凉山彝族自治州

    • 四川省

  • 南充市

    • 四川省

  • 宜宾市

    • 四川省

  • 巴中市

    • 四川省

  • 广元市

    • 四川省

  • 广安市

    • 四川省

  • 德阳市

    • 四川省

  • 成都市

    • 四川省

  • 攀枝花市

    • 四川省

  • 泸州市

    • 四川省

  • 甘孜藏族自治州

    • 四川省

  • 眉山市

    • 四川省

  • 绵阳市

    • 四川省

  • 自贡市

    • 四川省

  • 资阳市

    • 四川省

  • 达州市

    • 四川省

  • 遂宁市

    • 四川省

  • 阿坝藏族羌族自治州

    • 四川省

  • 雅安市

    • 天津市

  • 市辖区

    • 宁夏回族自治区

  • 中卫市

    • 宁夏回族自治区

  • 吴忠市

    • 宁夏回族自治区

  • 固原市

    • 宁夏回族自治区

  • 石嘴山市

    • 宁夏回族自治区

  • 银川市

    • 安徽省

  • 亳州市

    • 安徽省

  • 六安市

    • 安徽省

  • 合肥市

    • 安徽省

  • 安庆市

    • 安徽省

  • 宣城市

    • 安徽省

  • 宿州市

    • 安徽省

  • 池州市

    • 安徽省

  • 淮北市

    • 安徽省

  • 淮南市

    • 安徽省

  • 滁州市

    • 安徽省

  • 芜湖市

    • 安徽省

  • 蚌埠市

    • 安徽省

  • 铜陵市

    • 安徽省

  • 阜阳市

    • 安徽省

  • 马鞍山市

    • 安徽省

  • 黄山市

    • 山东省

  • 东营市

    • 山东省

  • 临沂市

    • 山东省

  • 威海市

    • 山东省

  • 德州市

    • 山东省

  • 日照市

    • 山东省

  • 枣庄市

    • 山东省

  • 泰安市

    • 山东省

  • 济南市

    • 山东省

  • 济宁市

    • 山东省

  • 淄博市

    • 山东省

  • 滨州市

    • 山东省

  • 潍坊市

    • 山东省

  • 烟台市

    • 山东省

  • 聊城市

    • 山东省

  • 菏泽市

    • 山东省

  • 青岛市

    • 山西省

  • 临汾市

    • 山西省

  • 吕梁市

    • 山西省

  • 大同市

    • 山西省

  • 太原市

    • 山西省

  • 忻州市

    • 山西省

  • 晋中市

    • 山西省

  • 晋城市

    • 山西省

  • 朔州市

    • 山西省

  • 运城市

    • 山西省

  • 长治市

    • 山西省

  • 阳泉市

    • 广东省

  • 东莞市

    • 广东省

  • 中山市

    • 广东省

  • 云浮市

    • 广东省

  • 佛山市

    • 广东省

  • 广州市

    • 广东省

  • 惠州市

    • 广东省

  • 揭阳市

    • 广东省

  • 梅州市

    • 广东省

  • 汕头市

    • 广东省

  • 汕尾市

    • 广东省

  • 江门市

    • 广东省

  • 河源市

    • 广东省

  • 深圳市

    • 广东省

  • 清远市

    • 广东省

  • 湛江市

    • 广东省

  • 潮州市

    • 广东省

  • 珠海市

    • 广东省

  • 肇庆市

    • 广东省

  • 茂名市

    • 广东省

  • 阳江市

    • 广东省

  • 韶关市

    • 广西壮族自治区

  • 北海市

    • 广西壮族自治区

  • 南宁市

    • 广西壮族自治区

  • 崇左市

    • 广西壮族自治区

  • 来宾市

    • 广西壮族自治区

  • 柳州市

    • 广西壮族自治区

  • 桂林市

    • 广西壮族自治区

  • 梧州市

    • 广西壮族自治区

  • 河池市

    • 广西壮族自治区

  • 玉林市

    • 广西壮族自治区

  • 百色市

    • 广西壮族自治区

  • 贵港市

    • 广西壮族自治区

  • 贺州市

    • 广西壮族自治区

  • 钦州市

    • 广西壮族自治区

  • 防城港市

    • 新疆维吾尔自治区

  • 乌鲁木齐市

    • 新疆维吾尔自治区

  • 伊犁哈萨克自治州

    • 新疆维吾尔自治区

  • 克孜勒苏柯尔克孜自治州

    • 新疆维吾尔自治区

  • 克拉玛依市

    • 新疆维吾尔自治区

  • 博尔塔拉蒙古自治州

    • 新疆维吾尔自治区

  • 吐鲁番市

    • 新疆维吾尔自治区

  • 和田地区

    • 新疆维吾尔自治区

  • 哈密市

    • 新疆维吾尔自治区

  • 喀什地区

    • 新疆维吾尔自治区

  • 塔城地区

    • 新疆维吾尔自治区

  • 巴音郭楞蒙古自治州

    • 新疆维吾尔自治区

  • 昌吉回族自治州

    • 新疆维吾尔自治区

  • 自治区直辖县级行政区划

    • 新疆维吾尔自治区

  • 阿克苏地区

    • 新疆维吾尔自治区

  • 阿勒泰地区

    • 江苏省

  • 南京市

    • 江苏省

  • 南通市

    • 江苏省

  • 宿迁市

    • 江苏省

  • 常州市

    • 江苏省

  • 徐州市

    • 江苏省

  • 扬州市

    • 江苏省

  • 无锡市

    • 江苏省

  • 泰州市

    • 江苏省

  • 淮安市

    • 江苏省

  • 盐城市

    • 江苏省

  • 苏州市

    • 江苏省

  • 连云港市

    • 江苏省

  • 镇江市

    • 江西省

  • 上饶市

    • 江西省

  • 九江市

    • 江西省

  • 南昌市

    • 江西省

  • 吉安市

    • 江西省

  • 宜春市

    • 江西省

  • 抚州市

    • 江西省

  • 新余市

    • 江西省

  • 景德镇市

    • 江西省

  • 萍乡市

    • 江西省

  • 赣州市

    • 江西省

  • 鹰潭市

    • 河北省

  • 保定市

    • 河北省

  • 唐山市

    • 河北省

  • 廊坊市

    • 河北省

  • 张家口市

    • 河北省

  • 承德市

    • 河北省

  • 沧州市

    • 河北省

  • 石家庄市

    • 河北省

  • 秦皇岛市

    • 河北省

  • 衡水市

    • 河北省

  • 邢台市

    • 河北省

  • 邯郸市

    • 河南省

  • 三门峡市

    • 河南省

  • 信阳市

    • 河南省

  • 南阳市

    • 河南省

  • 周口市

    • 河南省

  • 商丘市

    • 河南省

  • 安阳市

    • 河南省

  • 平顶山市

    • 河南省

  • 开封市

    • 河南省

  • 新乡市

    • 河南省

  • 洛阳市

    • 河南省

  • 漯河市

    • 河南省

  • 濮阳市

    • 河南省

  • 焦作市

    • 河南省

  • 省直辖县级行政区划

    • 河南省

  • 许昌市

    • 河南省

  • 郑州市

    • 河南省

  • 驻马店市

    • 河南省

  • 鹤壁市

    • 浙江省

  • 丽水市

    • 浙江省

  • 台州市

    • 浙江省

  • 嘉兴市

    • 浙江省

  • 宁波市

    • 浙江省

  • 杭州市

    • 浙江省

  • 温州市

    • 浙江省

  • 湖州市

    • 浙江省

  • 绍兴市

    • 浙江省

  • 舟山市

    • 浙江省

  • 衢州市

    • 浙江省

  • 金华市

    • 海南省

  • 三亚市

    • 海南省

  • 三沙市

    • 海南省

  • 儋州市

    • 海南省

  • 海口市

    • 海南省

  • 省直辖县级行政区划

    • 湖北省

  • 十堰市

    • 湖北省

  • 咸宁市

    • 湖北省

  • 孝感市

    • 湖北省

  • 宜昌市

    • 湖北省

  • 恩施土家族苗族自治州

    • 湖北省

  • 武汉市

    • 湖北省

  • 省直辖县级行政区划

    • 湖北省

  • 荆州市

    • 湖北省

  • 荆门市

    • 湖北省

  • 襄阳市

    • 湖北省

  • 鄂州市

    • 湖北省

  • 随州市

    • 湖北省

  • 黄冈市

    • 湖北省

  • 黄石市

    • 湖南省

  • 娄底市

    • 湖南省

  • 岳阳市

    • 湖南省

  • 常德市

    • 湖南省

  • 张家界市

    • 湖南省

  • 怀化市

    • 湖南省

  • 株洲市

    • 湖南省

  • 永州市

    • 湖南省

  • 湘潭市

    • 湖南省

  • 湘西土家族苗族自治州

    • 湖南省

  • 益阳市

    • 湖南省

  • 衡阳市

    • 湖南省

  • 邵阳市

    • 湖南省

  • 郴州市

    • 湖南省

  • 长沙市

    • 甘肃省

  • 临夏回族自治州

    • 甘肃省

  • 兰州市

    • 甘肃省

  • 嘉峪关市

    • 甘肃省

  • 天水市

    • 甘肃省

  • 定西市

    • 甘肃省

  • 平凉市

    • 甘肃省

  • 庆阳市

    • 甘肃省

  • 张掖市

    • 甘肃省

  • 武威市

    • 甘肃省

  • 甘南藏族自治州

    • 甘肃省

  • 白银市

    • 甘肃省

  • 酒泉市

    • 甘肃省

  • 金昌市

    • 甘肃省

  • 陇南市

    • 福建省

  • 三明市

    • 福建省

  • 南平市

    • 福建省

  • 厦门市

    • 福建省

  • 宁德市

    • 福建省

  • 泉州市

    • 福建省

  • 漳州市

    • 福建省

  • 福州市

    • 福建省

  • 莆田市

    • 福建省

  • 龙岩市

    • 西藏自治区

  • 山南市

    • 西藏自治区

  • 拉萨市

    • 西藏自治区

  • 日喀则市

    • 西藏自治区

  • 昌都市

    • 西藏自治区

  • 林芝市

    • 西藏自治区

  • 那曲市

    • 西藏自治区

  • 阿里地区

    • 贵州省

  • 六盘水市

    • 贵州省

  • 安顺市

    • 贵州省

  • 毕节市

    • 贵州省

  • 贵阳市

    • 贵州省

  • 遵义市

    • 贵州省

  • 铜仁市

    • 贵州省

  • 黔东南苗族侗族自治州

    • 贵州省

  • 黔南布依族苗族自治州

    • 贵州省

  • 黔西南布依族苗族自治州

    • 辽宁省

  • 丹东市

    • 辽宁省

  • 大连市

    • 辽宁省

  • 抚顺市

    • 辽宁省

  • 朝阳市

    • 辽宁省

  • 本溪市

    • 辽宁省

  • 沈阳市

    • 辽宁省

  • 盘锦市

    • 辽宁省

  • 营口市

    • 辽宁省

  • 葫芦岛市

    • 辽宁省

  • 辽阳市

    • 辽宁省

  • 铁岭市

    • 辽宁省

  • 锦州市

    • 辽宁省

  • 阜新市

    • 辽宁省

  • 鞍山市

    • 重庆市

  • 县

    • 重庆市

  • 市辖区

    • 陕西省

  • 咸阳市

    • 陕西省

  • 商洛市

    • 陕西省

  • 安康市

    • 陕西省

  • 宝鸡市

    • 陕西省

  • 延安市

    • 陕西省

  • 榆林市

    • 陕西省

  • 汉中市

    • 陕西省

  • 渭南市

    • 陕西省

  • 西安市

    • 陕西省

  • 铜川市

    • 青海省

  • 果洛藏族自治州

    • 青海省

  • 海东市

    • 青海省

  • 海北藏族自治州

    • 青海省

  • 海南藏族自治州

    • 青海省

  • 海西蒙古族藏族自治州

    • 青海省

  • 玉树藏族自治州

    • 青海省

  • 西宁市

    • 青海省

  • 黄南藏族自治州

    • 黑龙江省

  • 七台河市

    • 黑龙江省

  • 伊春市

    • 黑龙江省

  • 佳木斯市

    • 黑龙江省

  • 双鸭山市

    • 黑龙江省

  • 哈尔滨市

    • 黑龙江省

  • 大兴安岭地区

    • 黑龙江省

  • 大庆市

    • 黑龙江省

  • 牡丹江市

    • 黑龙江省

  • 绥化市

    • 黑龙江省

  • 鸡西市

    • 黑龙江省

  • 鹤岗市

    • 黑龙江省

  • 黑河市

    • 黑龙江省

  • 齐齐哈尔市