|
最進(jìn)思考全排列的算法，得奎哥啟發(fā)，貼出來(lái)，以備后用。不過(guò)原貼中有些許個(gè)小筆誤，我擅自改了幾處。
全排列的生成算法就是對(duì)于給定的字符集，用有效的方法將所有可能的全排列無(wú)重復(fù)無(wú)遺漏地枚舉出來(lái)。任何n個(gè)字符集的排列都可以與1～n的n個(gè)數(shù)字的排列一一對(duì)應(yīng)，因此在此就以n個(gè)數(shù)字的排列為例說(shuō)明排列的生成法。
n個(gè)字符的全體排列之間存在一個(gè)確定的線性順序關(guān)系。所有的排列中除最后一個(gè)排列外，都有一個(gè)后繼；除第一個(gè)排列外，都有一個(gè)前驅(qū)。每個(gè)排列的后繼都可以從它 的前驅(qū)經(jīng)過(guò)最少的變化而得到，全排列的生成算法就是從第一個(gè)排列開(kāi)始逐個(gè)生成所有的排列的方法。
全排列的生成法通常有以下幾種：
字典序法
遞增進(jìn)位數(shù)制法
遞減進(jìn)位數(shù)制法
鄰位交換法
遞歸類(lèi)算法
1.字典序法
字典序法中，對(duì)于數(shù)字1、2、3......n的排列，不同排列的先后關(guān)系是從左到右逐個(gè)比較對(duì)應(yīng)的數(shù)字的先后來(lái)決定的。例如對(duì)于5個(gè)數(shù)字的排列12354和12345，排列12345在前，排列12354在后。按照這樣的規(guī)定，5個(gè)數(shù)字的所有的排列中最前面的是12345，最后面的是54321。
字典序算法如下：
設(shè)P是1～n的一個(gè)全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1）從排列的右端開(kāi)始，找出第一個(gè)比右邊數(shù)字小的數(shù)字的序號(hào)j（j從左端開(kāi)始計(jì)算），即 j=max{i|pi<pi+1}
2）在pj的右邊的數(shù)字中，找出所有比pj大的數(shù)中最小的數(shù)字pk，即 k=min{i|pi>pj}（右邊的數(shù)從右至左是遞增的，因此k是所有大于pj的數(shù)字中序號(hào)最大者）
3）對(duì)換pi，pk
4）再將pj+1......pk-1pkpk+1......pn倒轉(zhuǎn)得到排列p’=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，這就是排列p的下一個(gè)下一個(gè)排列。
例如839647521是數(shù)字1～9的一個(gè)排列。從它生成下一個(gè)排列的步驟如下：
自右至左找出排列中第一個(gè)比右邊數(shù)字小的數(shù)字4 839647521
在該數(shù)字后的數(shù)字中找出比4大的數(shù)中最小的一個(gè)5 839647521
將5與4交換 839657421
將7421倒轉(zhuǎn) 839651247
所以839647521的下一個(gè)排列是839651247。
2.遞增進(jìn)位數(shù)制法
在遞增進(jìn)位制數(shù)法中，從一個(gè)排列求另一個(gè)排列需要用到中介數(shù)。如果用 ki表示排列p1p2...pi...pn中元素pi的右邊比pi小的數(shù)的個(gè)數(shù)，則排列的中介數(shù)就是對(duì)應(yīng)的排列k1 ...... ki...... kn-1。
例如排列839647521的中介數(shù)是72642321，7、2、6、......分別是排列中數(shù)字8、3、9、......的右邊比它小的數(shù)字個(gè)數(shù)。
中介數(shù)是計(jì)算排列的中間環(huán)節(jié)。已知一個(gè)排列，要求下一個(gè)排列，首先確定其中介數(shù)，一個(gè)排列的后繼，其中介數(shù)是原排列中介數(shù)加1，需要注意的是，如果中介數(shù)的末位kn-1+1=2，則要向前進(jìn)位，一般情形，如果ki+1=n-i+1，則要進(jìn)位，這就是所謂的遞增進(jìn)位制。例如排列839647521的中介數(shù)是72642321，則下一個(gè)排列的中介數(shù)是72642321+1=72643000（因?yàn)?+1=2，所以向前進(jìn)位，2+1=3，又發(fā)生進(jìn)位，所以下一個(gè)中介數(shù)是67342300）。得到中介數(shù)后，可根據(jù)它還原對(duì)應(yīng)得排列839651247。
算法如下：
中介數(shù)k1、k2、......、kn-1的各位數(shù)字順序表示排列中的數(shù)字n、n-1、......、2在排列中距右端的的空位數(shù)，因此，要按k1、k2、......、kn-1的值從右向左確定n、n-1、......、2的位置，并逐個(gè)放置在排列中：i放在右起的ki+1位，如果某位已放有數(shù)字，則該位置不算在內(nèi)，最后一個(gè)空位放1。
因此從67342300可得到排列849617523，它就是839647521的后一個(gè)排列。因?yàn)?最先放置，k1=6，9放在右起第7位，空出6個(gè)空位，然后是放8，k2=7，8放在右起第8位，但9占用一位，故8應(yīng)放在右起第9位，余類(lèi)推。
3.遞減進(jìn)位制數(shù)法
在遞增進(jìn)位制數(shù)法中，中介數(shù)的最低位是逢2進(jìn)1，進(jìn)位頻繁，這是一個(gè)缺點(diǎn)。把遞增進(jìn)位制數(shù)翻轉(zhuǎn),就得到遞減進(jìn)位制數(shù)。
839647521的中介數(shù)是67342221(k1k2...kn-1)，倒轉(zhuǎn)成為12224376(kn-1...k2k1)，這是遞減進(jìn)位制數(shù)的中介數(shù)：ki(i=n-1,n-2,...,2)位逢i向ki-1位進(jìn)1。給定排列p，p的下一個(gè)排列的中介數(shù)定義為p的中介數(shù)加1。例如p=839647521，p的中介數(shù)為12224376，p的下一個(gè)排列的中介數(shù)為12224376+1=12224377，由此得到p的下一個(gè)排列為893647521。
給定中介數(shù)，可用與遞增進(jìn)位制數(shù)法類(lèi)似的方法還原出排列。但在遞減進(jìn)位制數(shù)中，可以不先計(jì)算中介數(shù)就直接從一個(gè)排列求出下一個(gè)排列。具體算法如下：
1）如果p(i)=n且i!=0，則p(i)與p(i-1)交換
2）如果p(1)=n，則找出一個(gè)連續(xù)遞減序列9、8、......、i，將其從排列左端刪除，再以相反順序加在排列右端，然后將i-1與左邊的數(shù)字交換 (i - 1必然不在首位，否則連續(xù)遞減的序列應(yīng)該是9~i-1了)
例如p=893647521的下一個(gè)排列是983647521。求983647521的下一個(gè)排列時(shí)，因?yàn)?在最左邊且第2位為8，第3位不是7，所以將8和9從小到大排于最右端364752189，再將7與其左方數(shù)字對(duì)調(diào)得到983647521的下一個(gè)排列是367452189。又例如求987635421的下一個(gè)排列，只需要將9876從小到大排到最右端并將5與其左方數(shù)字3對(duì)調(diào)，得到534216789。
4.鄰位對(duì)換法
鄰位對(duì)換法中下一個(gè)排列總是上一個(gè)排列某相鄰兩位對(duì)換得到的。以4個(gè)元素的排列為例，將最后的元素4逐次與前面的元素交換，可以生成4個(gè)新排列：
1 2 3 4 1 2 4 3 1 4 2 3 4 1 2 3
然后將最后一個(gè)排列的末尾的兩個(gè)元素交換，再逐次將排頭的4與其后的元素交換，又生成四個(gè)新排列：
4 1 3 2 1 4 3 2 1 3 4 2 1 3 2 4
再將最后一個(gè)排列的末尾的兩個(gè)元素交換，將4從后往前移：
3 1 2 4 3 1 4 2 3 4 1 2 4 3 1 2
如此循環(huán)既可求出全部排列。
5.元素增值法（n進(jìn)制法）
1）從原始排列p=p1p2......pn開(kāi)始，第n位加n-1，如果該位的值超過(guò)n，則將它除以n，用余數(shù)取代該位，并進(jìn)位（將第n-1位加1）
2）再按同樣方法處理n-1位，n-2位，......，直至不再發(fā)生進(jìn)位為止，處理完一個(gè)排列就產(chǎn)生了一個(gè)新的排列
3）將其中有相同元素的排列去掉
4）當(dāng)?shù)谝粋€(gè)元素的值>n則結(jié)束
以3個(gè)數(shù)1、2、3的排列為例：原始排列是1 2 3，從它開(kāi)始，第3個(gè)元素是3，3+2=5，5 Mod 3=2，第2個(gè)元素是2，2+1=3，所以新排列是1 3 2。通過(guò)元素增值，順序產(chǎn)生的排列是：1 2 3，1 3 2，2 1 1，2 1 3，2 2 2，2 3 1，2 3 3，3 1 2，3 2 1
有下劃線的排列中存在重復(fù)元素，丟棄，余下的就是全部排列。
6.遞歸類(lèi)算法
全排列的生成方法用遞歸方式描述比較簡(jiǎn)潔，實(shí)現(xiàn)的方法也有多種。
1）回溯法
回溯法通常是構(gòu)造一顆生成樹(shù)。以3個(gè)元素為例；樹(shù)的節(jié)點(diǎn)有個(gè)數(shù)據(jù)，可取值是1、2、3。如果某個(gè)為0，則表示尚未取值。
初始狀態(tài)是(0，0，0)，第1個(gè)元素值可以分別挑選1，2，3，因此擴(kuò)展出3個(gè)子結(jié)點(diǎn)。用相同方法找出這些結(jié)點(diǎn)的第2個(gè)元素的可能值，如此反復(fù)進(jìn)行，一旦出現(xiàn)新結(jié)點(diǎn)的3個(gè)數(shù)據(jù)全非零，那就找到了一種全排列方案。當(dāng)嘗試了所有可能方案，即獲得了問(wèn)題的解答。
2）遞歸算法
如果用P表示n個(gè)元素的排列，而Pi表示不包含元素i的排列，(i)Pi表示在排列Pi前加上前綴i的排列，那么，n個(gè)元素的排列可遞歸定義為：
如果n=1，則排列P只有一個(gè)元素i
如果n>1，則排列P由排列(i)Pi構(gòu)成（i=1、2、....、n-1）。
根據(jù)定義，容易看出如果已經(jīng)生成了k-1個(gè)元素的排列，那么，k個(gè)元素的排列可以在每個(gè)k-1個(gè)元素的排列Pi前添加元素i而生成。例如2個(gè)元素的排列是1 2和2 1，對(duì)與個(gè)元素而言，p1是2 3和3 2，在每個(gè)排列前加上1即生成1 2 3和1 3 2兩個(gè)新排列，p2和p3則是1 3、3 1和1 2、2 1，按同樣方法可生成新排列2 1 3、2 3 1和3 1 2、3 2 1。
3）循環(huán)移位法
如果已經(jīng)生成了k-1個(gè)元素的排列，則在每個(gè)排列后添加元素k使之成為k個(gè)元素的排列，然后將每個(gè)排列循環(huán)左移（右移），每移動(dòng)一次就產(chǎn)生一個(gè)新的排列。
例如2個(gè)元素的排列是1 2和2 1。在1 2 后加上3成為新排列1 2 3，將它循環(huán)左移可再生成新排列2 3 1、3 1 2，同樣2 1 可生成新排列2 1 3、1 3 2和3 2 1。
view plaincopy to clipboardprint?
#include "stdafx.h"
#include<iostream>
using namespace std;
#include<time.h>
#define maxn 100
void outp(int p[],int n) //輸出一個(gè)排列
{
int i;
cout<<" ";
for(i=1;i<=n;i++)
cout<<p[i]<<" ";
cout<<endl;
}
void swap(int & x,int & y)
{
int t=x;
x=y;
y=t;
}
void dict(int p[],int n) //字典序法
{
int i,j;
outp(p,n);
i=n-1;
while(i>0)
{
if (p[i]<p[i+1])
{
for(j=n;j>=i+1;j--)
if(p[i]<=p[j]) break;
swap(p[i],p[j]);
for(j=n;j>=1;j--)
{
i+=1;
if (i>=j) break;
swap(p[i],p[j]);
}
outp(p,n);
i=n;
}
i-=1;
};
}
bool midn(int m[],int n)
{
int k=n-1;
while(1)
{
m[k]+=1;
if(m[k]<n-k+1)break;
m[k]=0;
k-=1;
}
int s=0;
bool b=false;
for( k=1;k<=n;)
s+=m[k++];
if(s==0) b=true;
return b;
}
void incr(int p[],int n)
{
int m[maxn];
int 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)
{
if(p[j]==0)
{
a-=1;
if(a==0) break;
}
j-=1;
}
p[j]=n-i+1;
}
outp(p,n);
if (midn(m,n)==true) break;
}
}
void degr(int p[],int n)
{
int i,j;
while(1)
{
outp(p,n);
if(p[1]!=n)
{
i=0;
while(p[++i]!=n);
swap(p[i],p[i-1]);
}
else
{
i=1;
while(i<n)
{
if(p[i]!=p[i+1]+1) break;
i+=1;
}
if(i==n)break;
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(int p[],int n)
{
long m=1;
for(int i=3;i<n;)
m=m*i++;
for(int i=1;i<m;i++)
{
outp(p,n);
for(int j=n;j>1;j--)
{
swap(p[j],p[j-1]);
outp(p,n);
}
swap(p[n],p[n-1]);
outp(p,n);
for(int j=1;j<n;j++)
{
swap(p[j],p[j+1]);
outp(p,n);
}
swap(p[1],p[2]);
}
}
bool test(int p[], int n)
{
bool b=false;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(p[i]==p[j])
{
b=true;
break;
}
return b;
}
void Nnum(int p[],int n)
{
while(n>0)
{
if (test(p,n)==false) outp(p,n);
p[n]+=n-1;
for(int j=n;j>1;j--)
{
if(p[j]>n)
{
p[j]%=n;
p[j-1]+=1;
if(p[1]>n)
{
n=0;
break;
}
}
}
}
}
void recu(int p[],int n,int k)
{
if(k==n)
outp (p,n);
else
{
for(int i=k;i<=n;i++)
{
swap (p[k],p[i]);
recu(p, n,k+1);
swap (p[k],p[i]);
}
}
}
void cyc(int p[],int n,int k)
{
if (k>n)
outp(p,n);
else
{
for(int i=0;i<k;i++)
{
int t=p[1];
for(int j=2;j<=k;j++)
p[j-1]=p[j];
p[k]=t;
cyc(p,n,k+1);
}
}
}
void remo(int p[],int n,int k)
{
bool b;
if (k>n)
outp (p,n);
else
{
for(int i=1;i<=n;i++)
{
b=false;
p[k]=i;
for(int j=1;j<k;j++)
if(i==p[j])
{
b=true;
break;
}
if(b==false) remo(p,n,k+1);
}
}
}
int main()
{
int i,j,m;
int p[maxn];
int n;
clock_t start,finish;
cout<<"輸入排列元素總數(shù)n=";
cin>>n;
for(i=1;i<=n;i++)
p[i]=i;
cout<<"1——字典序法"<<endl;
cout<<"2——遞增進(jìn)位數(shù)制法"<<endl;
cout<<"3——遞減進(jìn)位數(shù)制法"<<endl;
cout<<"4——鄰位交換法"<<endl;
cout<<"5——n進(jìn)制數(shù)法"<<endl;
cout<<"6——遞歸生成法"<<endl;
cout<<"7——循環(huán)移位法"<<endl;
cout<<"8——回溯法"<<endl;
cout<<"請(qǐng)選擇: ";
cin>>m;
start=clock();
switch (m)
{
case 1:dict(p,n);break;
case 2:incr(p,n);break;
case 3:degr(p,n);break;
case 4:conv(p,n);break;
case 5:Nnum(p,n);break;
case 6:recu(p,n,1);break;
case 7:cyc(p,n,1);break;
case 8:remo(p,n,1);
}
finish=clock();
cout<<"程序執(zhí)行時(shí)間："
<<(double)(finish-start)/CLOCKS_PER_SEC<<"秒"<<endl;
system("pause");
return 0;
}
#include "stdafx.h"
#include<iostream>
using namespace std;
#include<time.h>
#define maxn 100
void outp(int p[],int n) //輸出一個(gè)排列
{
int i;
cout<<" ";
for(i=1;i<=n;i++)
cout<<p[i]<<" ";
cout<<endl;
}
void swap(int & x,int & y)
{
int t=x;
x=y;
y=t;
}
void dict(int p[],int n) //字典序法
{
int i,j;
outp(p,n);
i=n-1;
while(i>0)
{
if (p[i]<p[i+1])
{
for(j=n;j>=i+1;j--)
if(p[i]<=p[j]) break;
swap(p[i],p[j]);
for(j=n;j>=1;j--)
{
i+=1;
if (i>=j) break;
swap(p[i],p[j]);
}
outp(p,n);
i=n;
}
i-=1;
};
}
bool midn(int m[],int n)
{
int k=n-1;
while(1)
{
m[k]+=1;
if(m[k]<n-k+1)break;
m[k]=0;
k-=1;
}
int s=0;
bool b=false;
for( k=1;k<=n;)
s+=m[k++];
if(s==0) b=true;
return b;
}
void incr(int p[],int n)
{
int m[maxn];
int 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)
{
if(p[j]==0)
{
a-=1;
if(a==0) break;
}
j-=1;
}
p[j]=n-i+1;
}
outp(p,n);
if (midn(m,n)==true) break;
}
}
void degr(int p[],int n)
{
int i,j;
while(1)
{
outp(p,n);
if(p[1]!=n)
{
i=0;
while(p[++i]!=n);
swap(p[i],p[i-1]);
}
else
{
i=1;
while(i<n)
{
if(p[i]!=p[i+1]+1) break;
i+=1;
}
if(i==n)break;
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(int p[],int n)
{
long m=1;
for(int i=3;i<n;)
m=m*i++;
for(int i=1;i<m;i++)
{
outp(p,n);
for(int j=n;j>1;j--)
{
swap(p[j],p[j-1]);
outp(p,n);
}
swap(p[n],p[n-1]);
outp(p,n);
for(int j=1;j<n;j++)
{
swap(p[j],p[j+1]);
outp(p,n);
}
swap(p[1],p[2]);
}
}
bool test(int p[], int n)
{
bool b=false;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(p[i]==p[j])
{
b=true;
break;
}
return b;
}
void Nnum(int p[],int n)
{
while(n>0)
{
if (test(p,n)==false) outp(p,n);
p[n]+=n-1;
for(int j=n;j>1;j--)
{
if(p[j]>n)
{
p[j]%=n;
p[j-1]+=1;
if(p[1]>n)
{
n=0;
break;
}
}
}
}
}
void recu(int p[],int n,int k)
{
if(k==n)
outp (p,n);
else
{
for(int i=k;i<=n;i++)
{
swap (p[k],p[i]);
recu(p, n,k+1);
swap (p[k],p[i]);
}
}
}
void cyc(int p[],int n,int k)
{
if (k>n)
outp(p,n);
else
{
for(int i=0;i<k;i++)
{
int t=p[1];
for(int j=2;j<=k;j++)
p[j-1]=p[j];
p[k]=t;
cyc(p,n,k+1);
}
}
}
void remo(int p[],int n,int k)
{
bool b;
if (k>n)
outp (p,n);
else
{
for(int i=1;i<=n;i++)
{
b=false;
p[k]=i;
for(int j=1;j<k;j++)
if(i==p[j])
{
b=true;
break;
}
if(b==false) remo(p,n,k+1);
}
}
}
int main()
{
int i,j,m;
int p[maxn];
int n;
clock_t start,finish;
cout<<"輸入排列元素總數(shù)n=";
cin>>n;
for(i=1;i<=n;i++)
p[i]=i;
cout<<"1——字典序法"<<endl;
cout<<"2——遞增進(jìn)位數(shù)制法"<<endl;
cout<<"3——遞減進(jìn)位數(shù)制法"<<endl;
cout<<"4——鄰位交換法"<<endl;
cout<<"5——n進(jìn)制數(shù)法"<<endl;
cout<<"6——遞歸生成法"<<endl;
cout<<"7——循環(huán)移位法"<<endl;
cout<<"8——回溯法"<<endl;
cout<<"請(qǐng)選擇: ";
cin>>m;
start=clock();
switch (m)
{
case 1:dict(p,n);break;
case 2:incr(p,n);break;
case 3:degr(p,n);break;
case 4:conv(p,n);break;
case 5:Nnum(p,n);break;
case 6:recu(p,n,1);break;
case 7:cyc(p,n,1);break;
case 8:remo(p,n,1);
}
finish=clock();
cout<<"程序執(zhí)行時(shí)間："
<<(double)(finish-start)/CLOCKS_PER_SEC<<"秒"<<endl;
system("pause");
return 0;
}
不知道大家有沒(méi)有聽(tīng)說(shuō),明年起程序員考試就不分初,中,高級(jí)了,而我們軟件專(zhuān)業(yè)明年就要過(guò)程序了,據(jù)說(shuō)相當(dāng)于考中程,或者還要難一些,雖然不知道消息的正確性,但這的確是我們的老師告訴我們的,所以老師就出一些題給我們練,下面是一道關(guān)于數(shù)學(xué)中全排列的算法的問(wèn)題,編了我4天!真是的看起來(lái)容易,編起來(lái)難..........下面給出我的源代碼,并給大家解釋思路:
view plaincopy to clipboardprint?
#include "stdio.h"
void chang(char str[],int m)
{
int i,j;
char temp=str[0];
for (i=0;i<m;i++) str[i]=str[i+1];
str[i]=temp;
}
void pai(char str[],int m,int n)
{
int k;
void chang(char str[],int m);
if (m<n)
{
for (k=0;k<=m;k++)
{
pai(str,m+1,n);
chang(str,m);
}
}
else printf("%s\t",str);
}
main()
{
char str[]="ABCD";
clrscr();
pai(str,0,4);
getch();
}
#include "stdio.h"
void chang(char str[],int m)
{
int i,j;
char temp=str[0];
for (i=0;i<m;i++) str[i]=str[i+1];
str[i]=temp;
}
void pai(char str[],int m,int n)
{
int k;
void chang(char str[],int m);
if (m<n)
{
for (k=0;k<=m;k++)
{
pai(str,m+1,n);
chang(str,m);
}
}
else printf("%s\t",str);
}
main()
{
char str[]="ABCD";
clrscr();
pai(str,0,4);
getch();
}
大家看到了,以上就是一步一步循環(huán)左移就能得到所有全排列的數(shù)了.以上程序在Trubo C 2.0 中運(yùn)行通過(guò),如果大家還有什么疑問(wèn),請(qǐng)加我QQ:156301529,Email:rodgersnow@163.com,我們共同討論.另外,我在想,如果是n個(gè)數(shù)或字符中取m個(gè)進(jìn)行排列的話,該怎么改呢?
view plaincopy to clipboardprint?
char t;
if (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;
}
} else
{
printf("%s\n", a);
}
}
int main() {
char a[]="ABCDE";
permutation(a, 0,5);
return 0;
}
|
