全排列
生成算法就是对于给定
集
用有效思路方法将所有可能全排列无重复无遗漏地枚举出来
任何n个集排列都可以和1～nn个数字排列
对应因此在此就以n个数字排列为例介绍说明排列生成法 n个
全体排列的间存在个确定线性顺序关系所有排列中除最后个排列外都有个后继；除第个排列外都有个前驱每个排列后继都可以从 它 前驱经过最少变化而得到全排列生成算法就是从第个排列开始逐个生成所有排列思路方法 全排列
生成法通常有以下几种: 字典序法
递增进位数制法
递减进位数制法
邻位交换法
递归类算法
1.字典序法
字典序法中
对于数字1、2、3......n排列区别排列先后关系是从左到右逐个比较对应数字先后来决定例如对于5个数字排列12354和12345排列12345在前排列12354在后按照这样规定5个数字所有排列中最前面是12345最后面是54321 字典序算法如下:
设P是1～n
个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn 1)从排列
右端开始找出第个比右边数字小数字序号j(j从左端开始计算)即 j=max{i|pi<pi+1} 2)在pj
右边数字中找出所有比pj大数中最小数字pk即 k=max{i|pi>pj}(右边数从右至左是递增因此k是所有大于pj数字中序号最大者) 3)对换pi
pk 4)再将pj+1......pk-1pkpk+1pn倒转得到排列p''=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1
这就是排列p下个下个排列 例如839647521是数字1～9
个排列从它生成下个排列步骤如下: 自右至左找出排列中第
个比右边数字小数字4 839647521 在该数字后
数字中找出比4大数中最小个5 839647521 将5和4交换 839657421
将7421倒转 839651247
所以839647521
下个排列是839651247 2.递增进位数制法
在递增进位制数法中
从个排列求另个排列需要用到中介数如果用 ki表示排列p1p2...pi...pn中元素pi右边比pi小数个数则排列中介数就是对应排列k1 ...... ki...... kn-1 例如排列839647521
中介数是726423217、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=69放在右起第7位空出6个空位然后是放8k2=78放在右起第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给定排列pp下个排列中介数定义为p中介数加1例如p=839647521p中介数为12224376p下个排列中介数为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个新排列: 1 2 3 4 1 2 4 3 1 4 2 3 4 1 2 3
然后将最后
个排列末尾两个元素交换再逐次将排头4和其后元素交换又生成 4个新排列: 4 1 3 2 1 4 3 2 1 3 4 2 1 3 2 4
再将最后
个排列末尾两个元素交换将4从后往前移: 3 1 2 4 3 1 4 2 3 4 1 2 4 3 1 2
如此循环既可求出全部排列
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
排列为例:原始排列是1 2 3从它开始第3个元素是33+2=55 Mod 3=2第2个元素是22+1=3所以新排列是1 3 2通过元素增值顺序产生排列是:1 2 31 3 22 1 12 1 32 2 22 3 12 3 33 1 23 2 1 有下划线
排列中存在重复元素丢弃余下就是全部排列 6.递归类算法
全排列
生成思路方法用递归方式描述比较简洁实现思路方法也有多种 1)回溯法
回溯法通常是构造
颗生成树以3个元素为例；树节点有个数据可取值是1、2、3如果某个为0则表示尚未取值 
状态是(000)第1个元素值可以分别挑选123因此扩展出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个元素排列是1 2和2 1对和个元素而言p1是2 3和3 2在每个排列前加上1即生成1 2 3和1 3 2两个新排列p2和p3则是1 3、3 1和1 2、2 1按同样思路方法可生成新排列2 1 3、2 3 1和3 1 2、3 2 1 3)循环移位法
如果已经生成了k-1个元素
排列则在每个排列后添加元素k使的成为k个元素排列然后将每个排列循环左移(右移)每移动次就产生个新排列 例如2个元素
排列是1 2和2 1在1 2 后加上3成为新排列1 2 3将它循环左移可再生成新排列2 3 1、3 1 2同样2 1 可生成新排列2 1 3、1 3 2和3 2 1 view plaincopy to clipboardpr
? #
"stdafx.h" #
<iostream> using
std; #
<time.h> #
maxn 100 void outp(
p
, n) //输出个排列 {
i; cout<<" ";
for(i=1;i<=n;i
) cout<<p[i]<<" ";
cout<<endl;
}
void swap(
& x, & y) {
t=x; x=y;
y=t;
}
void dict(
p, n) //字典序法 {
i,j; outp(p,n);
i=n-1;
while(i>0)
{
(p[i]<p[i+1]) {
for(j=n;j>=i+1;j--)
(p[i]<=p[j]) 
; swap(p[i],p[j]);
for(j=n;j>=1;j--)
{
i
1; (i>=j) ; swap(p[i],p[j]);
}
outp(p,n);
i=n;
}
i-=1;
};
}
bool midn(
m, n) {
k=n-1; while(1)
{
m[k]
1; (m[k]<n-k+1); m[k]=0;
k-=1;
}
s=0; bool b=false;
for( k=1;k<=n;)
s
m[k]; (s
0) b=true; 
b; }
void incr(
p, n) {
m[maxn]; i,j,a; for(i=1;i<=n;)
m[i
]=0; while(i>0)
{
for(i=1;i<=n;)
p[i
]=0; for(i=1;i<=n;i
) {
a=m[i]+1;
j=n;
while(j>0)
{
(p[j]0) {
a-=1;
(a0) ; }
j-=1;
}
p[j]=n-i+1;
}
outp(p,n);
(midn(m,n)true) ; }
}
void degr(
p, n) {
i,j; while(1)
{
outp(p,n);
(p[1]!=n) {
i=0;
while(p[
i]!=n); swap(p[i],p[i-1]);
}
{
i=1;
while(i<n)
{
(p[i]!=p[i+1]+1) ; i
1; }
(in); j=i;
while(p[i]!=p[j]-1)
i
1; swap(p[i],p[i-1]);
for(i=1;i<=n-j;)
p[i
]=p[i+j]; for (i=1;i<=j;i
) p[n-i+1] =n-i+1;
}
}
}
void conv(
p, n) {
long m=1;
for(
i=3;i<n;) m=m*i
; for(
i=1;i<m;i) {
outp(p,n);
for(
j=n;j>1;j--) {
swap(p[j],p[j-1]);
outp(p,n);
}
swap(p[n],p[n-1]);
outp(p,n);
for(
j=1;j<n;j) {
swap(p[j],p[j+1]);
outp(p,n);
}
swap(p[1],p[2]);
}
}
bool test(
p, n) {
bool b=false;
for(
i=1;i<=n;i) for(
j=i+1;j<=n;j) (p[i]p[j]) {
b=true;
; }
b; }
void Nnum(
p, n) {
while(n>0)
{
(test(p,n)false) outp(p,n); p[n]
n-1; for(
j=n;j>1;j--) {
(p[j]>n) {
p[j]%=n;
p[j-1]
1; (p[1]>n) {
n=0;
; }
}
}
}
}
void recu(
p, n, k) {
(kn) outp (p,n);
{
for(
i=k;i<=n;i) {
swap (p[k],p[i]);
recu(p, n,k+1);
swap (p[k],p[i]);
}
}
}
void cyc(
p, n, k) {
(k>n) outp(p,n);
{
for(
i=0;i<k;i) {
t=p[1]; for(
j=2;j<=k;j) p[j-1]=p[j];
p[k]=t;
cyc(p,n,k+1);
}
}
}
void remo(
p, n, k) {
bool b;
(k>n) outp (p,n);
{
for(
i=1;i<=n;i) {
b=false;
p[k]=i;
for(
j=1;j<k;j) (ip[j]) {
b=true;
; }
(bfalse) remo(p,n,k+1); }
}
}
{
i,j,m; p[maxn]; n; clock_t start,finish;
cout<<"输入排列元素总数n=";
cin>>n;
for(i=1;i<=n;i
) p[i]=i;
cout<<"1——字典序法"<<endl;
cout<<"2——递增进位数制法"<<endl;
cout<<"3——递减进位数制法"<<endl;
cout<<"4——邻位交换法"<<endl;
cout<<"5——n进制数法"<<endl;
cout<<"6——递归生成法"<<endl;
cout<<"7——循环移位法"<<endl;
cout<<"8——回溯法"<<endl;
cout<<"请选择: ";
cin>>m;
start=clock
; switch (m)
{
1:dict(p,n);; 2:incr(p,n);; 3:degr(p,n);; 4:conv(p,n);; 5:Nnum(p,n);; 6:recu(p,n,1);; 7:cyc(p,n,1);; 8:remo(p,n,1); }
finish=clock
; cout<<"
执行时间:" <<(double)(finish-start)/CLOCKS_PER_SEC<<"秒"<<endl;
system("pause");
0; }
#
"stdafx.h" #
<iostream> using
std; #
<time.h> #
maxn 100 void outp(
p, n) //输出个排列 {
i; cout<<" ";
for(i=1;i<=n;i
) cout<<p[i]<<" ";
cout<<endl;
}
void swap(
& x, & y) {
t=x; x=y;
y=t;
}
void dict(
p, n) //字典序法 {
i,j; outp(p,n);
i=n-1;
while(i>0)
{
(p[i]<p[i+1]) {
for(j=n;j>=i+1;j--)
(p[i]<=p[j]) ; swap(p[i],p[j]);
for(j=n;j>=1;j--)
{
i
1; (i>=j) ; swap(p[i],p[j]);
}
outp(p,n);
i=n;
}
i-=1;
};
}
bool midn(
m, n) {
k=n-1; while(1)
{
m[k]
1; (m[k]<n-k+1); m[k]=0;
k-=1;
}
s=0; bool b=false;
for( k=1;k<=n;)
s
m[k]; (s0) b=true; b; }
void incr(
p, n) {
m[maxn]; i,j,a; for(i=1;i<=n;)
m[i
]=0; while(i>0)
{
for(i=1;i<=n;)
p[i
]=0; for(i=1;i<=n;i
) {
a=m[i]+1;
j=n;
while(j>0)
{
(p[j]0) {
a-=1;
(a0) ; }
j-=1;
}
p[j]=n-i+1;
}
outp(p,n);
(midn(m,n)true) ; }
}
void degr(
p, n) {
i,j; while(1)
{
outp(p,n);
(p[1]!=n) {
i=0;
while(p[
i]!=n); swap(p[i],p[i-1]);
}
{
i=1;
while(i<n)
{
(p[i]!=p[i+1]+1) ; i
1; }
(in); j=i;
while(p[i]!=p[j]-1)
i
1; swap(p[i],p[i-1]);
for(i=1;i<=n-j;)
p[i
]=p[i+j]; for (i=1;i<=j;i
) p[n-i+1] =n-i+1;
}
}
}
void conv(
p, n) {
long m=1;
for(
i=3;i<n;) m=m*i
; for(
i=1;i<m;i) {
outp(p,n);
for(
j=n;j>1;j--) {
swap(p[j],p[j-1]);
outp(p,n);
}
swap(p[n],p[n-1]);
outp(p,n);
for(
j=1;j<n;j) {
swap(p[j],p[j+1]);
outp(p,n);
}
swap(p[1],p[2]);
}
}
bool test(
p, n) {
bool b=false;
for(
i=1;i<=n;i) for(
j=i+1;j<=n;j) (p[i]p[j]) {
b=true;
; }
b; }
void Nnum(
p, n) {
while(n>0)
{
(test(p,n)false) outp(p,n); p[n]
n-1; for(
j=n;j>1;j--) {
(p[j]>n) {
p[j]%=n;
p[j-1]
1; (p[1]>n) {
n=0;
; }
}
}
}
}
void recu(
p, n, k) {
(kn) outp (p,n);
{
for(
i=k;i<=n;i) {
swap (p[k],p[i]);
recu(p, n,k+1);
swap (p[k],p[i]);
}
}
}
void cyc(
p, n, k) {
(k>n) outp(p,n);
{
for(
i=0;i<k;i) {
t=p[1]; for(
j=2;j<=k;j) p[j-1]=p[j];
p[k]=t;
cyc(p,n,k+1);
}
}
}
void remo(
p, n, k) {
bool b;
(k>n) outp (p,n);
{
for(
i=1;i<=n;i) {
b=false;
p[k]=i;
for(
j=1;j<k;j) (ip[j]) {
b=true;
; }
(bfalse) remo(p,n,k+1); }
}
}
{
i,j,m; p[maxn]; n; clock_t start,finish;
cout<<"输入排列元素总数n=";
cin>>n;
for(i=1;i<=n;i
) p[i]=i;
cout<<"1——字典序法"<<endl;
cout<<"2——递增进位数制法"<<endl;
cout<<"3——递减进位数制法"<<endl;
cout<<"4——邻位交换法"<<endl;
cout<<"5——n进制数法"<<endl;
cout<<"6——递归生成法"<<endl;
cout<<"7——循环移位法"<<endl;
cout<<"8——回溯法"<<endl;
cout<<"请选择: ";
cin>>m;
start=clock
; switch (m)
{
1:dict(p,n);; 2:incr(p,n);; 3:degr(p,n);; 4:conv(p,n);; 5:Nnum(p,n);; 6:recu(p,n,1);; 7:cyc(p,n,1);; 8:remo(p,n,1); }
finish=clock
; cout<<"
执行时间:" <<(double)(finish-start)/CLOCKS_PER_SEC<<"秒"<<endl;
system("pause");
0; }
不知道大家有没有听说,明年起
员考试就不分初,中,高级了,而我们软件Software专业明年就要过了,据说相当于考中程,或者还要难些,虽然不知道消息正确性,但这确是我们老师告诉我们,所以老师就出些题给我们练,下面是道有关数学中全排列算法问题,编了我4天!真是看起来容易,编起来难..........下面给出我源代码,并给大家解释我思路: view plaincopy to clipboardpr
? #
"stdio.h" void chang(char str
, m) /*定义循环左移
(我没有用左移)*/ {
i,j; char temp=str[0];
for (i=0;i<m;i
) str[i]=str[i+1]; str[i]=temp;
}
void pai(char str
, m, n) /*定义全排列*/ {
k; void chang(char str
, m); (m<n) /* 定 义 递 归 调 用 出 口 */ {
for (k=0;k<=m;k
) {
pai(str,m+1,n); /*递归
*/ chang(str,m); /*
左移*/ }
}
prf("%s\t",str); }
{
char str
="ABCD"; /*全排列,可以任意多个(相应下面排列中参数"4"改成全排列个数)*/ clrscr
; pai(str,0,4); /*这里参数0(下标)表示从第
个元素开始,4表示元素个数(不是下标)*/ getch
; }
#
"stdio.h" void chang(char str
, m) /*定义循环左移(我没有用左移)*/ {
i,j; char temp=str[0];
for (i=0;i<m;i
) str[i]=str[i+1]; str[i]=temp;
}
void pai(char str
, m, n) /*定义全排列*/ {
k; void chang(char str
, m); (m<n) /* 定 义 递 归 调 用 出 口 */ {
for (k=0;k<=m;k
) {
pai(str,m+1,n); /*递归
*/ chang(str,m); /*
左移*/ }
}
prf("%s\t",str); }
{
char str
="ABCD"; /*全排列,可以任意多个(相应下面排列中参数"4"改成全排列个数)*/ clrscr
; pai(str,0,4); /*这里参数0(下标)表示从第
个元素开始,4表示元素个数(不是下标)*/ getch
; }
大家看到了,以上就是
步步循环左移就能得到所有全排列数了.以上在Trubo C 2.0 中运行通过,如果大家还有什么疑问,请加我QQ:156301529,Email:[email protected],我们共同讨论.另外,我在想,如果是n个数或中取m个进行排列话,该如何改呢?目前正在考虑中,本人觉得难度很大,希望大家能帮帮我,请加我QQ,谢谢! 另附我在网上找到
经典全排列算法,叫"后补法",大家自己好好研究吧,在Trubo C 2.0 中运行通过了. view plaincopy to clipboardpr
? char t;
(m<n-1) { permutation(a, m+1, n);
for (i=m+1;i<n;i
) { t=a[m]; a[m]=a[i]; a[i]=t;
permutation(a, m+1, n);
t=a[m]; a[m]=a[i]; a[i]=t;
}
}
{
pr
f("%s\n", a); }
}
{ char a
="ABCDE"; permutation(a, 0,5);
0; }
最新评论