全排列的生成算法:字典序法
全排列的生成算法
字典序法
递增进位数制法
递减进位数制法
邻位交换法
n进位制法
递归类算法
1.字典序法
字典序算法如下:
设P是1~n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1)从排列的右端开始,找出第一个比右边数字小的数字的序号j(j从左端开始计算),即
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
在该数字后的数字中找出比4大的数中最小的一个5
将5与4交换
将7421倒转
所以839647521的下一个排列是839651247。
程序代码如下:
Private Sub Dict(p() As Integer, ByVal n As Integer)
Dim i As Integer, j As Integer
OutL p
i = n - 1
Do While i > 0
For j = n To i + 1 Step -1
If p(i) <= p(j) Then Exit For
Next
Swap p(i), p(j)
For j = n To 1 Step -1
i = i + 1
If i >= j Then Exit For
Swap p(i), p(j)
Next
OutL p
i = n
Loop
End Sub
Swap p(i), p(j)是交换两个元素的子过程,OutL p是输出排列的子过程。
2.递增进位数制法
例如排列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位,余类推。
程序代码如下:
Private Sub Incr(p() As Integer, ByVal n As Integer)
Dim m() As Integer
Dim i As Integer, j As Integer
Dim a As Integer
ReDim m(n)
For i = 1 To n
Next
Do While n > 0
p(i) = 0
a = m(i) + 1
j = n
Do While j > 0
If p(j) = 0 Then
End If
j = j - 1
Loop
p(j) = n - i + 1
Loop
End Sub
Private Function MedN(m() As Integer)As Boolean
Dim i As Integer, sum As Integer
Dim b As Boolean
b = False
i = n - 1
Do While i > 0
Loop
Sum = 0
For i = 1 To n - 1
Next
If Sum = 0 Then b = True
MedN = b
End Function
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。
程序代码如下:
Private Sub Degr(p() As Integer, ByVal n As Integer)
Dim i As Integer, j As Integer
Do While n > 0
i = 0
Do
i = i + 1
If i = n Then Exit Sub
Loop Until p(i) <> p(i + 1) + 1
j = i
Do
i = i + 1
Loop Until p(i) = p(j) - 1
Swap p(i), p(i - 1)
For i = 1 To n - j
p(i) = p(i + j)
Next
For i = 1 To j
p(n - i + 1) = n - i + 1
Next
i = 0
Do
i = i + 1
Loop Until p(i) = n
Swap p(i), p(i - 1)
Loop
End Sub
4.邻位对换法
1 2 3 4
3 1 2 4
Private Sub Adja(p() As Integer, ByVal n As Integer)
m = 1
For i = 3 To n - 1
Next
For i = 1 To m - 1
Swap p(j), p(j - 1)
OutL p
Swap p(j), p(j + 1)
OutL p
Next
End Sub
5.元素增值法(n进制法)
1)从原始排列p=p1p2......pn开始,第n位加n-1,如果该位的值超过n,则将它除以n,用余数取代该位,并进位(将第n-1位加1)
2)再按同样方法处理n-1位,n-2位,......,直至不再发生进位为止,处理完一个排列就产生了一个新的排列
3)将其中有相同元素的排列去掉
4)当第一个元素的值>n则结束
Private Sub Incr(p() As Integer, ByVal n As Integer)
OutL p
Nextn:
If p(j) > n Then
p(j) = p(j) Mod n
p(j - 1) = p(j - 1) + 1
If p(1) > n Then Exit Sub
End If
For j = i + 1 To n
If p(i) = p(j) Then GoTo Nextn '排列中有重复元素,丢弃
Next
Loop
End Sub
6.递归类算法
1)回溯法
回溯法通常是构造一颗生成树。以3个元素为例;树的节点有个数据,可取值是1、2、3。如果某个为0,则表示尚未取值。
初始状态是(0,0,0),第1个元素值可以分别挑选1,2,3,因此扩展出3个子结点。用相同方法找出这些结点的第2个元素的可能值,如此反复进行,一旦出现新结点的3个数据全非零,那就找到了一种全排列方案。当尝试了所有可能方案,即获得了问题的解答。
程序代码如下:
Private Sub Remo(p() As Integer, ByVal k As Integer)
OutL p
For i = 1 To n
p(k) = i
For j = 1 To k - 1
End If
Next
If Not b Then Remo, k + 1
End If
End Sub
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
程序代码如下:
Private Sub Recu(p() As Integer, ByVal k As Integer)
OutL p
For i = k To n
Next
End Sub
3)循环移位法
程序代码如下:
Private Sub Cycl(p() As Integer,ByVal k As Integer)
If k > n Then
Else
t = p(1)
For j = 2 To k
p(j - 1) = p(j)
Next
p(k) = t
Cycl
End If
End Sub
C++全排列之非递归算法:字典序法
题目:1~n的全排列
思想:(字典序法)初始化数组为1,2,3,...,n作为开端;设法从后续排列中找到大于前次结果但小于其他结果的序列;依此找出这样的序列(后面序列肯定大于前面序列),则最后一个序列肯定是n,...,3,2,1
步骤:
假设情景:找“*243”该序列的下一个后续序列从后往前找,找到这样一个数,它后面的数更大,(即找到"*24*",取2作为当前数,下标为i)在“2”的后面,找到最接近2且比2大的数,这里找到“3”(下标为j)调换a[i]和a[j]的值对a[i+1]……a[n-1]进行转置此时数组a中的数就是所求后续序列从1,2,3,...,n依此求出后续序列(即重新进行上面步骤),一直找到i=0且a[0]>a[1]则算法结束,全排列已全部给出。
三思:
怎么保证后面的序列比前面的大?首先开端是序列中最小的,i后面的部分是倒叙排列的,再对调(保证了大于前面序列)后,对i后面的进行逆置,保证了自身是后续排列中最小的,所以小于前面大于后面,依此递增,直到n,...,3,2,1算法结束。该算法要给一个开端,对于求“142”全排列这种情况,是不是还需要进行先排序得到“124”后再处理?该算法对调操作频繁,还有转置操作,相比较于递归调用函数,时间更少了,但心里不是滋味。处理"1223"这种情况又怎样?递归方法不能处理,但这种方法可以处理。对于字符排序"abc","abb"这两种情况,貌似与数字排序"123","122"一样,反正字符也可以比较大小,所以这两种情况也可以得到解决。
其他:头文件#include<algorithm>提供字典序法求后续序列的函数为next_permutation(_, _)。
代码:
#include <iostream>usingnamespacestd;constintMaxNum=9;intiArr[MaxNum];intcount;inlinevoidprintArr(intn)//打印数组,n为元素的总个数{inti;for(i=0;i<n;i++)cout<<iArr[i];cout<<endl;count++;}inlinevoidSwap(inti,intj)//调换iArr[i]与iArr[j]的值{inttemp=iArr[i];iArr[i]=iArr[j];iArr[j]=temp;}voidTranspose(intk,intm)//把数组下标为k~m的数转置{inti,j;for(i=k,j=m;j>i;i++,j--)Swap(i,j);}intFullArray2(constintn)//对1~n进行全排列{if(1==n){cout<<"1"<<endl;count++;return1;}//特殊情况n=1inti,j;while(1){printArr(n);for(i=n-2;i>=0;i--){//要求n>=2if(iArr[i]<iArr[i+1])break;//先求iif(0==i)return1;//函数出口:当i=0且iArr[0]>iArr[1]时,函数结束}for(j=n-1;j>i;j--){if(iArr[i]<iArr[j])break;//后求j}Swap(i,j);//调换iArr[i]与iArr[j]的值Transpose(i+1,n-1);//把i后面的数转置}}voidmain(){inti,n;while(1){system("cls");count=0;//测试新用例时,count重新置0cout<<"请输入n(最大为9):";cin>>n;if(n>MaxNum || n<1){cout<<"Error: n的值在设定值范围之外"<<endl;break;}for(i=0;i<n;i++)iArr[i]=i+1;//由于FullArray2上一次调用完,不会把调换的元素调整回来,故每次调用FullArray2前都要对数组进行重新初始化,即这条语句不能放在while循环外。FullArray2(n);cout<<"1~"<<n<<"的全排列的个数:"<<count<<endl;system("pause");}}
来源:/s/blog_4cd4ffc401018x7r.html
如果觉得《全排列的生成算法:字典序法》对你有帮助,请点赞、收藏,并留下你的观点哦!