全排列问题的求解算法及相关应用

全排列问题的求解算法及相关应用

李曼生

(兰州师范高等专科学校数学系,甘肃兰州730030)

摘要:给出了1至n全排列问题的二种求解算法,分析了该问题在栈中的应用。关键词:算法;栈;数据结构

中图分类号:TG386

1引言

在很多问题求解中,都会用到1...n各种全排列,我们知道1...n自然数的全排列共有n!种,那么如何设计算法用计算机打印出1...n的所有全排列呢?当n是某一个固定值时,可以轻而易举地通过n重循环算法完成此功能。但是要对任意n值实现算法,却并不容易实现。本文给出了二种实现此功能的算法,分析了算法的时间复杂度,并介绍了具体应用的例子。

2求解算法

以下算法均用delphi语句描述。

2.1算法1:用数组模拟n重循环

该算法设立一个数组a,来模拟n重循环的n 个循环控制变量,每次循环时判断n个循环控制变量是否完全不同,如果不同则是一个全排列。循环完一次以后,要改变最内层循环的循环控制变量值,内层循环完以后,再进行外层循环。在数组a中,a [1]表示最外层循环控制变量,a[n]表示最内层循环控制变量。a的初值如下设置:

a[1]a[2]a[3]...a[n]

123...n

procedure p(n:integer);

var a:array[1..100]of integer;

con:boolean;

i,j,k,m:longint;

op:string;//储存字符串输出

begin

for i:=1to n do a[i]:=i;//为a赋初值

m:=0;//计数全排列的数量

while a[1]

begin

con:=true;j:=1;

while(j<=n)and con do

begin

for k:=1to j-1do

if a[k]=a[j]then con:=false;

j:=j+1

end;//判断a数组中n个循环控制变量是否不同

if con then//con为真,输出a数组中全排列

begin

m:=m+1;//全排列的数量加1

op:=..;

for i:=1to n do

op:=op+..+inttostr(a[i]);

//输出op

end;

k:=n;//最内层循环

a[k]:=a[k]+1;//最内层循环控制变量加1

if a[k]>n then//最内层循环完毕

begin//依次修改各循环控制变量

while(a[k]>n)and(k>1)do

begin

k:=k-1;a[k]:=a[K]+1;

end;

k:=k+1;

while k<=n do

begin

第21卷第4期2005年4月

甘肃科技

Gansu Science and T echnology

V ol.21No.4

Apr il.2005

a[k]:=1;k:=k+1;

end;

end;

end;//n重循环end

end;//过程p结束

该算法是用数组模拟一个n重循环,其时间复杂度是o(nn),算法虽然通过给a赋初值的办法,减少了很多循环次数,但不影响算法的整个时间复杂度。

2.2算法2:递归形式实现

该算法设立一个全局a数组,存储产生n个数全排列的中间结果。kkk是一个递归过程,参数y 表示递归的层次,在进行第y层递归调用时在a数组中已经排列好全排列的前y-1个值,该层调用时主要产生全排列的第y个值,并进行y+1层的递归调用,当进行到第n+1层调用时可输出a数组的全排列。

procedure p(n:integer);

var

a:array[1...100]of integer;

m:integer;

op:string;//储存字符串输出

procedure kkk(y:integer);//递归过程

var

i,q,j:integer;

begin

if k=n+1then//输出a数组中的全排列

begin

m:=m+1;

op:=..;

for i:=1to n do

op:=op+..+inttostr(a[i]);

//输出op

exit;

end;

for j:=1to n do//循环查找第y个数

begin

a[y]:=j;//给全排列的第y个数赋值

q:=0;//检查第y个值与前y-1个值是否相同

for i:=1to y-1do

if a[i]=j then q:=q+1;

if q=0then//q=0则第y个值正确

kkk(y+1);//y+1层调用

end;

end;

begin

m:=0;//计数全排列的数量

kkk(1);//调用递归过程

end;

该算法很简洁,但却又很难理解,粗看起来这好像是用递归形式模拟n重循环,但算法的执行效率却远比n重循环高效的多。仔细分析,影响算法效率的应该是递归调用的次数,因为每一层递归调用的次数,直接影响着深层次调用的次数,整个算法的递归调用次数为:n*(n-1)*(n-2)*...*2*1 *1,因此算法时间复杂度应该是o(n!)的。

3二种算法比较

以上二个算法均能实现输出1...n的所有全排列,也给出了算法时间复杂度的分析,很显然算法1时间复杂度是较高的。算法2好一些,因为主循环恰好为n!次。为了进一步验证分析结果,我们在一台cpu为1GHZ,内存为256M的机器上进行了验证,结果如下表:

N值7891011

算法10秒3秒55秒1450秒很长时间

算法20秒1秒5秒53秒664秒

排列数504040320362880362880039916800从表中可以看到算法2的执行效率更高一些。

4全排列在栈中的应用

栈(stack)是一种后进先出的数据结构,当某一个输入序列顺序进栈时可以得到不同的出栈序列,如1,2,3三个数顺序进栈可以得到123,132,321, 231,213五种不同出栈序列。对于一般问题,当有1,2,...,n共n个数顺序进栈,可以得到多少种不同的出栈序列呢?对于此问题我们可以借助如下结论:[1]

若借助栈由输入序列12...n得到的输出序列是p1p2...pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着i

证明:反证法

假设存在这样的输出序列,因为i

75

第4期李曼生:安排列问题的求解算法及相关应用

上)))地面的唯一信息通道。为了抗牵引电流的干扰以及实现列车定位,轨间电缆每隔一定距离(例如每隔25m)作一交叉。一个中继器最多可控128个电缆环路。所以一个中继器的最大控制距离为: Lcmax=128@25=3200m。

利用轨间电缆的交叉配置即可实现列车定位。在此情况下,我们可用14位电码来表示列车的地址信息。最高位bit位为列车运行方向码,第11~ 13bit为相位中继器的代码,第4~10bit为粗地址码,表明列车处于哪一个电缆环路。每当列车驶过一个电缆交叉点。利用信号极性的变化引发粗地址码的末位码加1,第1~3bit表示细地址码,列车每驶过3.13m(25m@1/8),细地址码的末位码加1。

例:控制中心收到列车的地址码为:

10010010110100

译码后可知:1)方向码为1则列车为上行方向;

2)中继器代码为001(1#中继器);3)粗地址码: 0010110y42,即列车位于第42环路;4)细地址码: 100y4,即列车位于第42环路的中央(距始端12.5米处)。

最后的定位结论为:该列车位于1#中继器的控制区内,离1#中继器始端的距离为:42@25+ 12.5=1062.5m。

采用轨间电缆的超速防护系统的车载设备,包括接收天线、车载计算机、发送及接收电路、操作及指示盘、与制动机的接口、路程脉冲发生器等。

中继器的框图结构图略。中继器是控制中心与轨间电缆之间的中间环节,它的功能是把控制中心的命令通过轨间电缆传给机车,将机车信息传至控制中心。

3.3系统软件概述

要求系统的反应十分灵敏,即要求数据处理的速度很高,所以将与列车运行有关的区间数据表、列车数据表分别储存在计算机的内存中,由操作系统控制数据的存入和取出。

区间数据表中的数据分成静态数据和动态数据两大类:

动态数据:区间设备状态的变化,缓行段的增减,紧急停车操作(车上或经由联锁设备)。静态数据:区间设备的地点,区间坡度,缓行段的位置和长度,列车接发地点,区间的分界点,每一段轨间电缆的地理位置等。

列车数据表中储存全部与列车有关的信息,由于控制中心整个管辖区内的列车是运动的,所以列车数据表中的数据都是动态数据(包括列车的制动率,即时速度,所处的位置等等),它的接收、监视、删除都用程序来完成。列车数据表以级联的方式构成,从而可使每列车知道它的前行和后续车的位置。

对于每一个具体区间,在设计完成后就能提供一份完整的区间数据文件,借助于翻译程序就可自动生成区间数据表。

这种系统的信息传递的连续性是以昂贵的轨间电缆为代价的,而且轨间电缆的存在给线路养护工作带来了麻烦(养路工作容易损坏轨间电缆)。

参考文献:

[1]吴汶麒.国外铁路信号新技术[M].北京:中国铁道出

版社,2000。

(上接第75页)定晚于pk出栈,因此这与所假设出栈序列中pj比pk早矛盾。(证毕)

利用此结论及前面求1,2,...,n全排列的算法,可以求得当1,2,...,n共n个数顺序进栈时可以得到的所有出栈序列。具体做法是:当得到一个具体排列时,用如下算法判断该排列能否由栈得到。

function test:boolean;

//判断是否为一个出栈序列,假设排列存储在a数组中

var i,j,k:integer;

con:boolean;

begin

con:=true;

for i:=0to n-3do

for j:=i to n-2do

for k:=j to n-1do

if(a[j]

test:=con;//返回结果

end;

参考文献:

[1]严蔚敏,吴伟民.数据结构题集(C语言版)[M].北京:

清华大学出版社,2000.84-85

[2]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华

大学出版社,2000.35-36

[3] C.C.Gotlieb and L.R.Gotlieb,Data Types and Struc2

tures[D],by prent ice-Hall Inc.,1978.

81

第4期王祖华:浅析连续式列车速度自动控制系统