《全排列算法解析》由会员分享，可在线阅读，更多相关《全排列算法解析（16页珍藏版）》请在金锄头文库上搜索。
1、全排列以及相关算法在程序设计过程中，我们往往要对一个序列进行全排列或者对每一个排列进行分析。全排列算法便是用于产生全排列或者逐个构造全排列的方法。当然，全排列算法不仅仅止于全排列，对于普通的排列，或者组合的问题，也可以解决。本文主要通过对全排列以及相关算法的介绍和讲解、分析，让读者更好地了解这一方面的知识，主要涉及到的语言是C和C+。本文的节数：1全排列的定义和公式：2. 时间复杂度：3列出全排列的初始思想：4从第m个元素到第11个元素的全排列的算法：5. 全排列算法：6. 全排列的字典序：7求下一个字典序排列算法：8.C+STL库中的next_permutation0函数：(#include
2、)9字典序的中介数，由中介数求序号：10.由中介数求排列：11递增进位制数法：12递减进位制数法：13.邻位对换法：14邻位对换法全排列：15邻位对换法的下一个排列：16邻位对换法的中介数：17组合数的字典序与生成：由于本文的，内容比较多，所以希塑读者根据自己的要求阅读，不要一次性读完，有些章节可以分开读。第1节到第5节提供了全排列的概念和一个初始的算法。第6节到第8节主要讲述了字典序的全排列算法。第9到第10节讲了有关字典序中中介数的概念。第11到第12节主要介绍了不同的中介数方法，仅供扩展用。第13节到15节介绍了邻位对换法的全排的有关知识。16节讲了有关邻位对换法的中介数，仅供参考。第1
3、7节讲了组合数生成的算法。1全排列的定义和公式：从n个数中选取m(m=n)个数按照一定的顺序进行排成一个列，叫作从11个元素中取m个元素的一个排列。由排列的定义，显然不同的顺序是一个不同的排列。从n个元素中取in个元素的所有排列的个数，称为排列数。从11个元素取出n个元素的一个排列，称为一个全排列。全排列的排列数公式为n!,通过乘法原理可以得到。2. 时间复杂度：n个数(字符、对象)的全排列一共有n!种，所以全排列算法至少时O(n!)的。如果要对全排列进行输出，那么输出的时间要O(n*n!),因为每一个排列都有n个数据。所以实际上，全排列算法对大型的数据是无法处理的，而一般情况下也不会要求我们
4、去遍历一个大型数据的全排列。3. 列出全排列的初始思想：解决一个算法问题，我比较习惯于从基本的想法做起，我们先回顾一下我们自己是如何写一组数的全排列的：1，3,5,9(为了方便，下面我都用数进行全排列而不是字符)。1, 3,5,9.（第一个）首先保持第一个不变，对3,5,9进行全排列。同样地，我们先保持3不变，对5,9进行全排列。保持5不变，对9对进行全排列，由于9只有一个，它的排列只有一种：9。接下来5不能以5打头了，5,9相互交换，得到1,3,9,5.此时5,9的情况都写完了，不能以3打头了，得到1,5,3,91,5,9,31,9,3,51,9,5,3这样，我们就得到了1开头的所有排列，这
5、是我们一般的排列数生成的过程。再接看是以3、5、9打头，得到全排列。这里还要注意的一点是，对于我们人而言，我们脑子里相当于是储存了一张表示原有数组的表，1,3,5,9,1开头的所有排列完成后，我们选择3开头，3选完了之后，我们选择5开头，而不会再返过来选1,而且知道选到9之后结束，但对于计算机而言，我们得到了3,5,1,9后，可能再次跳到1当中，因为原来数组的顺序它已经不知道了，这样便产生了错误。对于算法的设计，我们也可以维护这样一个数组，它保存了原始的数据，这是一种方法。同时我们还可以再每次交换后再交换回来，变回原来的数组，这样程序在遍历的时候便不会出错。读者可以练习一下这个过程，思考一下你
6、是如何进行全排列的，当然，你的方法可能和我的不太一样。我们把上面全排列的方法归纳一下，基本上就是：任意选一个数（一般从小到大或者从左到右）打头，刘后面的n-1个数进行全排列。聪明的读者应该已经发现，这是一个递归的方法,因为要得到ml个数的全排列，我们又要先去得到m2个数的全排列，而出I是只有1个数的全排列，因为它只有1种，为它的本身。写成比较规范的流程：1-开始for循环。2改变第一个元素为原始数组的第一个元素（什么都没做）。3求第2个元素到第n个元素的全排列。4要求第2个元素到第n个元素的全排列，要递归的求第3个元素到第n个元素的全排列。5直到递归到第n个元素到第n元素的全排列，递归出II。
7、6将改变的数组变回。7改变第一个元素为原始数组的第二个元素。（注：理论上来说第:次排升时才改变了第一个兀素，即第6步应该此时才开始执行，但由于多执行一次无义的交换影响不犬，而这样使得算法没有特殊情况，更容易读懂，如果一定省时间可以把这步写在此处，这种算法我在下文中便不给出了，读者可以口C写。）5求第2个元素到第n个元素的全排列。6要求第2个元素到第n个元素的全排列，要递归的求第3个元素到第n个元素的全排列。5直到递归到第n个元素到第n元素的全排列，递归出II。6将改变的数组变回。8不断地改变第一个元素，直至n次使for循环中止。为了实现上述过程，我们要先得到从第m个元素到第n个元素的排列的算法
8、:4从第m个元素到第11个元素的全排列的算法：voidPennutation(mtA,mtm,mtn)if(m=n)Pnnt(A);直接输出，因为前n-1个数已经确定，递归到只有1个数。return;elsefor(i=in;in;i+)进入for循环，对应第一步swap(am,ai);/交换,对应第:步Permutation(A,m+1,n);递I丿I调用,对应匸至/l步swap(am,ai);/交换,对应第六步为了使代码运行更快，Prmt函数和swap函数直接写成表达式而不是函数(如果是C+的话建议把swap写成内联函数，把Print写成宏)voidPennutation(mtA,mtm,
9、mtn)mti,mttemp;if(m=n)fbr(i=0;in;i+)if(i!=n-1)pnntf(”d”,Ai);有加空格elsepnntf(“d“Ai);没加空格直接输出，因为前n-1个数已经确定，递归到只有1个数。return;elsefor(i=in;ib(k+l),则称排列c位于排列b(关于字典序)的后面。如1，2,3,4的字典序排在1,2,4,3的前面(k=2),1,3,2,4的字典序在1,2,3,4(k=l)的后面。下面列出1,2,3按字典序的排列结杲：1,2,31, 3,22, 1,32, 3,13, 1,23, 2,1(有些读者会发现它们手写排列的时候也不自觉得遵照着这个
10、规则以妨漏写，对于计算机也一样，如果有这样习惯的读者的话，那它们的实际算法更适合于表达为下面要讲的算法。)定义字典序的好处在于，排列变得有序了，而我们前面的递归算法的排列是无序的，由同一个序列生成的不同数组(排列)如1,2,3,4和2,3,4,1的输出结呆的顺序是不同的，这样便没有统一性，而字典序则可以解决这个问题。很明显地，对于一个元素各不相同的元素集合,它的每个排列的字典序位置都不相同，有先有后。接下来讲讲如何求某一个排列的紧邻着的后一个字典序。对证明不感兴趣的读者只要读下面加色的字即可。定理：我们先来构造这样一个在它后面的字典序，再证明这是紧邻它的字典序。对于一个排列al,a2,a3.a
11、n,如果a(n)a(n-l),那么al,a2,a3a(n),a(nl)是它后面的字典序,否则，也就是a(n-l)a(n),此时如果a(n-2)a(m)【如果a(n)Va(n-l),则找a(n-l)和a(n-2),不断迭代，直到找到这样一组数或者m=l还不满足，则有a(l)a.a(n),是最大的字典序】，显然后面的序列满足a(m+l)a(m+2).a(n)找到a(m+l)到a(n)中比a(m)大的最小的数，和a(m)交换，并把交换后的a(m+l)到a(n)按照从小到大排序，前m-1项保持不变，得到的显然也是原排列后面的字典序，这个字典序便是紧挨着排列的后一个字典序。下面证明它是紧挨着的。1如果还
12、存在前m-1项和原排列相同并且也在原排列后面的字典序al,a2,a3.bm,.-1)111原am,假设它在我们构造的字典序前面，那么必有binv交换后的am,但这是不可能的，因为am是后面序列中大于原来am的最小的一个，而bin必然又是后面序列中的大于ani的一个元素，产生了矛盾。2如果还存在前前in项和原排列相同并且也在原排列后面的字典序，它不可能在我们构造的字典序前面，因为我们对后面的数进行了升序排列，不存在比a(m+l)还小的数。3-如果还存在前k项(kvm-1)和原排列相同并且也在原排列后面的字典序，它更不可能在我们构造的字典序前而，因为b(k+l)a(k+l)k+l=0;i-)if(Ai+lAi)break;if(i0)retiunfalse;m=i;i+;fdr(;in;i-H-)if(Ai=Am)i-Sbreak;swap(Ai,Am);sort(A+m+l,A+n);Pnnt(A);returntine;swap和Pimt函数读者可以自己写也可以参照我上面的写法，排序我这里直接使用了C+标准库中的sort,读者也可以自己写。有了这个算法后，我们便可以写一个非递归的列出全排
