全排列C编程Word文档格式.docx
- 文档编号:6372656
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:16
- 大小:19.46KB
全排列C编程Word文档格式.docx
《全排列C编程Word文档格式.docx》由会员分享,可在线阅读,更多相关《全排列C编程Word文档格式.docx(16页珍藏版)》请在冰点文库上搜索。
#39;
&
=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1,这就是排列p的下一个下一个排列。
例如839647521是数字1~9的一个排列。
从它生成下一个排列的步骤如下:
自右至左找出排列中第一个比右边数字小的数字4839647521
在该数字后的数字中找出比4大的数中最小的一个5839647521
将5与4交换839657421
将7421倒转839651247
所以839647521的下一个排列是839651247。
2.递增进位数制法
在递增进位制数法中,从一个排列求另一个排列需要用到中介数。
如果用ki表示排列p1p2...pi...pn中元素pi的右边比pi小的数的个数,则排列的中介数就是对应的排列k1......ki......kn-1。
例如排列839647521的中介数是72642321,7、2、6、......分别是排列中数字8、3、9、......的右边比它小的数字个数。
中介数是计算排列的中间环节。
已知一个排列,要求下一个排列,首先确定其中介数,一个排列的后继,其中介数是原排列中介数加1,需要注意的是,如果中介数的末位kn-1+1=2,则要向前进位,一般情形,如果ki+1
=n-i+1,则要进位,这就是所谓的递增进位制。
例如排列839647521的中介数是72642321,则下一个排列的中介数是67342221+1=67342300(因为1+1=2,所以向前进位,2+1=3,又发生进位,所以下一个中介数是67342300)。
得到中介数后,可根据它还原对应得排列。
算法如下:
中介数k1、k2、......、kn-1的各位数字顺序表示排列中的数字n、n-1、......、2在排列中距右端的的空位数,因此,要按k1、k2、......、kn-1的值从右向左确定n、n-1、......、2的位置,并逐个放置在排列中:
i放在右起的ki+1位,如果某位已放有数字,则该位置不算在内,最后一个空位放1。
因此从67342300可得到排列849617523,它就是839647521的后一个排列。
因为9最先放置,k1=6,9放在右起第7位,空出6个空位,然后是放8,k2=7,8放在右起第8位,但9占用一位,故8应放在右起第9位,余类推。
3.递减进位制数法
在递增进位制数法中,中介数的最低位是逢2进1,进位频繁,这是一个缺点。
把递增进位制数翻转,就得到递减进位制数。
839647521的中介数是67342221(k1k2…kn-1),倒转成为12224376(kn-1…k2k1),这是递减进位制数的中介数:
ki(i=n-1,n-2,…,2)位逢i向ki-1位进1。
给定排列p,p的下一个排列的中介数定义为p的中介数加1。
例如p=839647521,p的中介数为12224376,p的下一个排列的中介数为12224376+1=12224377,由此得到p的下一个排列为893647521。
给定中介数,可用与递增进位制数法类似的方法还原出排列。
但在递减进位制数中,可以不先计算中介数就直接从一个排列求出下一个排列。
具体算法如下:
1)如果p(i)=n且i&
n,则p(i)与p(i-1)交换
2)如果p(n)=n,则找出一个连续递减序列9、8、......、i,将其从排列左端删除,再以相反顺序加在排列右端,然后将i-1与左边的数字交换
例如p=893647521的下一个排列是983647521。
求983647521的下一个排列时,因为9在最左边且第2位为8,第3位不是7,所以将8和9从小到大排于最右端364752189,再将7与其左方数字对调得到983647521的下一个排列是367452189。
又例如求987635421的下一个排列,只需要将9876从小到大排到最右端并将5与其左方数字3对调,得到534216789。
4.邻位对换法
邻位对换法中下一个排列总是上一个排列某相邻两位对换得到的。
以4个元素的排列为例,将最后的元素4逐次与前面的元素交换,可以生成4个新排列:
1234124314234123
然后将最后一个排列的末尾的两个元素交换,再逐次将排头的4与其后的元素交换,又生成四个新排列:
4132143213421324
再将最后一个排列的末尾的两个元素交换,将4从后往前移:
3124314234124312
如此循环既可求出全部排列。
5.元素
增值法(n进制法)
1)从原始排列p=p1p2......pn开始,第n位加n-1,如果该位的值超过n,则将它除以n,用余数取代该位,并进位(将第n-1位加1)
2)再按同样方法处理n-1位,n-2位,......,直至不再发生进位为止,处理完一个排列就产生了一个新的排列
3)将其中有相同元素的排列去掉
4)当第一个元素的值&
n则结束
以3个数1、2、3的排列为例:
原始排列是123,从它开始,第3个元素是3,3+2=5,5Mod3=2,第2个元素是2,2+1=3,所以新排列是132。
通过元素增值,顺序产生的排列是:
123,132,211,213,222,231,233,312,321
有下划线的排列中存在重复元素,丢弃,余下的就是全部排列。
6.递归类算法
全排列的生成方法用递归方式描述比较简洁,实现的方法也有多种。
1)回溯法
回溯法通常是构造一颗生成树。
以3个元素为例;
树的节点有个数据,可取值是1、2、3。
如果某个为0,则表示尚未取值。
初始状态是(0,0,0),第1个元素值可以分别挑选1,2,3,因此扩展出3个子结点。
用相同方法找出这些结点的第2个元素的可能值,如此反复进行,一旦出现新结点的3个数据全非零,那就找到了一种全排列方案。
当尝试了所有可能方案,即获得了问题的解答。
2)递归算法
如果用P表示n个元素的排列,而Pi表示不包含元素i的排列,(i)Pi表示在排列Pi前加上前缀i的排列,那么,n个元素的排列可递归定义为:
如果n=1,则排列P只有一个元素i
如果n&
1,则排列P由排列(i)Pi构成(i=1、2、....、n-1)。
根据定义,容易看出如果已经生成了k-1个元素的排列,那么,k个元素的排列可以在每个k-1个元素的排列Pi前添加元素i而生成。
例如2个元素的排列是12和21,对与个元素而言,p1是23和32,在每个排列前加上1即生成123和132两个新排列,p2和p3则是13、31和12、21,按同样方法可生成新排列213、231和312、321。
3)循环移位法
如果已经生成了k-1个元素的排列,则在每个排列后添加元素k使之成为k个元素的排列,然后将每个排列循环左移(右移),每移动一次就产生一个新的排列。
例如2个元素的排列是12和21。
在12后加上3成为新排列123,将它循环左移可再生成新排列231、312,同样21可生成新排列213、132和321。
上述算法的程序代码如下:
#include&
iostream.h&
time.h&
constmaxn=100;
voidoutp(intp[],intn)//输出一个排列
{
inti;
cout&
quot;
&
;
for(i=1;
i&
=n;
i++)
p[i]&
endl;
}
voidswap(int&
amp;
x,int&
y)
intt=x;
x=y;
y=t;
voiddict(intp[],intn)//字典序法
inti,j;
outp(p,n);
i=n-1;
while(i&
0)
i
f(p[i]&
p[i+1])
for(j=n;
j&
=i+1;
j--)
if(p[i]&
=p[j])break;
swap(p[i],p[j]);
=1;
i+=1;
if(i&
=j)break;
i=n;
i-=1;
};
boolmidn(intm[],intn)
intk=n-1;
while
(1)
m[k]+=1;
if(m[k]&
n-k+1)break;
m[k]=0;
k-=1;
ints=0;
boolb=false;
for(k=1;
k&
)
s+=m[k++];
if(s==0)b=true;
returnb;
voidincr(intp[],intn)
intm[maxn];
inti,j,a;
m[i++]=0;
p[i++]=0;
a=m[i]+1;
j=n;
while(j&
if(p[j]==0)
a-=1;
if(a==0)break;
j-=1;
p[j]=n-i+1;
if(midn(m,n)==true)break;
voiddegr(intp[],intn)
if(p[1]!
=n)
i=0;
while(p[++i]!
=n);
swap(p[i],p[i-1]);
else
i=1;
n)
if(p[i]!
=p[i+1]+1)break;
if(i==n)break;
j=i;
while(p[i]!
=p[j]-1)
=n-j;
p[i++]=p[i+j];
for(i=1;
=j;
p[n-i+1]=n-i+1;
voidconv(intp[],intn)
longm=1;
for(inti=3;
n;
m=m*i++;
m;
for(intj=n;
1;
swap(p[j],p[j-1]);
swap(p[n],p[n-1]);
for(j=1;
j++)
swap(p[j],p[j+1]);
swap(p[1],p[2]);
booltest(intp[],intn)
for(inti=1;
for(intj=i+1;
if(p[i]==p[j])
b=true;
break;
voidNnum(intp[],intn)
while(n&
if(test(p,n)==false)outp(p,n);
p[n]+=n-1;
if(p[j]&
p[j]%=n;
p[j-1]+=1;
if(p[1]&
n=0;
}
voidrecu(intp[],intn,intk)
if(k==n)
outp(p,n);
for(inti=k;
swap(p[k],p[i]);
recu(p,n,k+1);
voidcyc(intp[],intn,intk)
if(k&
for(inti=0;
k;
intt=p[1];
for(intj=2;
=k;
p[j-1]=p[j];
p[k]=t;
cyc(p,n,k+1);
voidremo(intp[],intn,intk)
boolb;
b=false;
p[k]=i;
for(intj=1;
if(i==p[j])
if(b==false)remo(p,n,k+1);
voidmain()
inti,j,m;
intp[maxn];
intn;
clock_tstart,finish;
输入排列元素总数n=&
cin&
p[i]=i;
1——字典序法&
2——递增进位数制法&
3——递减进位数制法&
4——邻位交换法&
5——n进制数法&
6——递归生成法&
7——循环移位法&
8——回溯法&
请选择:
cin&
start=clock();
switch(m)
case1:
dict(p,n);
case2:
incr(p,n);
case3:
degr(p,n);
case4:
conv(p,n);
case5:
Nnum(p,n);
case6:
recu(p,n,1);
case7:
cyc(p,n,1);
case8:
remo(p,n,1);
finish=clock();
程序执行时间:
(double)(finish-start)/CLOCKS_PER_SEC&
秒&
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排列 编程