全排列算法1

全排列以及相关算法

　　在程序设计过程中，我们往往要对一个序列进行全排列或者对每一个排列进行分析。全排列算法便是用于产生全排列或者逐个构造全排列的方法。当然，全排列算法不仅仅止于全排列，对于普通的排列，或者组合的问题，也可以解决。本文主要通过对全排列以及相关算法的介绍和讲解、分析，让读者更好地了解这一方面的知识，主要涉及到的语言是C和C 。 本文的节数：

　　1.全排列的定义和公式：

　　2.时间复杂度：

　　3.列出全排列的初始思想：

　　4.从第m个元素到第n个元素的全排列的算法：

　　5.全排列算法：

　　6.全排列的字典序：

　　7.求下一个字典序排列算法：

　　8.C STL库中的next_permutation()函数：（#include）

　　9.字典序的中介数，由中介数求序号：

　　10.由中介数求排列：

　　11.递增进位制数法：

　　12.递减进位制数法：

　　13.邻位对换法：

　　14.邻位对换法全排列：

　　15.邻位对换法的下一个排列：

　　16.邻位对换法的中介数：

　　17.组合数的字典序与生成：

　　由于本文的，内容比较多，所以希望读者根据自己的要求阅读，不要一次性读完，有些章节可以分开读。第1节到第5节提供了全排列的概念和一个初始的算法。第6节到第8节主要讲述了字典序的全排列算法。第9到第10节讲了有关字典序中中介数的概念。第11到第12节主要介绍了不同的中介数方法，仅供扩展用。第13节到15节介绍了邻位对换法的全排的有关知识。16节讲了有关邻位对换法的中介数，仅供参考。第17节讲了组合数生成的算法。

　　1.全排列的定义和公式：

　　从n个数中选取m（m<=n）个数按照一定的顺序进行排成一个列，叫作从n个元素中取m个元素的一个排列。由排列的定义，显然不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数，称为排列数。从n个元素取出n个元素的一个排列，称为一个全排列。全排列的排列数公式为n!，通过乘法原理可以得到。

　　2.时间复杂度：

　　n个数（字符、对象）的全排列一共有n!种，所以全排列算法至少时O(n!)的。如果要对全排列进行输出，那么输出的时间要O(n*n!)，因为每一个排列都有n个数据。所以实际上，全排列算法对大型的数据是无法处理的，而一般情况下也不会要求我们去遍历一个大型数据的全排列。

　　3.列出全排列的初始思想：

　　解决一个算法问题，我比较习惯于从基本的想法做起，我们先回顾一下我们自己是如何写一组数的全排列的：1，3，5，9（为了方便，下面我都用数进行全排列而不是字符）。

　　1/16页

　　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，9

　　1，5，9，3

　　1，9，3，5

　　1，9，5，3

　　这样，我们就得到了1开头的所有排列，这是我们一般的排列数生成的过程。再接着是以3、5、9打头，得到全排列。这里还要注意的一点是，对于我们人而言，我们脑子里相当于是储存了一张表示原有数组的表，1，3，5，9，1开头的所有排列完成后，我们选择3开头，3选完了之后，我们选择5开头，而不会再返过来选1，而且知道选到9之后结束，但对于计算机而言，我们得到了3，5，1，9后，可能再次跳到1当中，因为原来数组的顺序它已经不知道了，这样便产生了错误。对于算法的设计，我们也可以维护这样一个数组，它保存了原始的数据，这是一种方法。同时我们还可以再每次交换后再交换回来，变回原来的数组，这样程序在遍历的时候便不会出错。读者可以练习一下这个过程，思考一下你是如何进行全排列的，当然，你的方法可能和我的不太一样。

　　我们把上面全排列的方法归纳一下，基本上就是：任意选一个数（一般从小到大或者从左到右）打头，对后面的n-1个数进行全排列。聪明的读者应该已经发现，这是一个递归的方法，因为要得到n-1个数的全排列，我们又要先去得到n-2个数的全排列，而出口是只有1个数的全排列，因为它只有1种，为它的本身。写成比较规范的流程：

　　1.开始for循环。

　　2.改变第一个元素为原始数组的第一个元素（什么都没做）。

　　3.求第2个元素到第n个元素的全排列。

　　4.要求第2个元素到第n个元素的全排列，要递归的求第3个元素到第n个元素的全排列。 ......

　　5.直到递归到第n个元素到第n元素的全排列，递归出口。

　　6.将改变的数组变回。

　　7.改变第一个元素为原始数组的第二个元素。

　　（注：理论上来说第二次排列时才改变了第一个元素，即第6步应该此时才开始执行，但由于多执行一次无义的交换影响不大，而这样使得算法没有特殊情况，更容易读懂，如果一定要省时间可以把这步写在此处，这种算法我在下文中便不给出了，读者可以自己写。）

　　5.求第2个元素到第n个元素的全排列。

　　6.要求第2个元素到第n个元素的全排列，要递归的求第3个元素到第n个元素的全排列。 ......

　　5.直到递归到第n个元素到第n元素的全排列，递归出口。

　　6.将改变的数组变回。

　　......

　　8.不断地改变第一个元素，直至n次使for循环中止。

　　为了实现上述过程，我们要先得到从第m个元素到第n个元素的排列的算法：

　　2/16页

　　4.从第m个元素到第n个元素的全排列的算法：

　　void Permutation(int A[], int m, int n)

　　{

　　if(m = = n)

　　{

　　Print(A); //直接输出，因为前n-1个数已经确定，递归到只有1个数。

　　return;

　　}

　　else

　　{

　　for(i=m;i<n;i )
　{

　　swap(a[m],a[i]); //交换，对应第二步

　　Permutation(A,m 1,n); //递归调用，对应三至五步

　　swap(a[m],a[i]); //交换，对应第六步

　　}

　　}

　　为了使代码运行更快，Print函数和swap函数直接写成表达式而不是函数（如果是C 的话建议把swap写成内联函数，把Print写成宏）

　　void Permutation(int A[], int m, int n)

　　{

　　int i, int temp;

　　if(m = = n)

　　{

　　for(i = 0;i　　{

　　if(i != n-1)

　　printf('%d ',A[i]); //有加空格

　　else

　　printf('%d' A[i]); //没加空格

　　} //直接输出，因为前n-1个数已经确定，递归到只有1个数。

　　printf('\n');

　　return;

　　}

　　else

　　{

　　for(i=m;i　　3/16页

　　是递归调用，对应的是第m个元素到第n个元素的全排列。*/

　　{

　　temp = A[m];

　　A[m] = A[i];

　　A[i] = temp; //交换，对应第二步

　　Permutation(A,m 1,n); //递归调用，对应三至五步

　　temp = A[m];

　　A[m] = A[i];

　　A[i] = temp;

　　//交换，对应第六步

　　}

　　}

　　}

　　这个算法用于列出从第m个元素到第n个元素的所有排列，注意n不一定是指最后一个元素。算法的复杂度在于for循环和递归，最大的for是n，递归为n-1所以为

　　O(n*n-1*n-2*...1) = O(n!).

　　对上述算法进行封装，便可以得到列出全排列的函数：

　　5.全排列算法：

　　void Full_Array(int A[],int n)

　　{

　　Permutation(A, 0,n);

　　}

　　如果读者仅仅需要一个全排列的递归算法，那么看到上面就可以了。下面将对全排列的知识进行扩充。

　　6.全排列的字典序：

　　字典序的英语一般叫做dictionary order,浅显明白。

　　定义：对于一个序列a1,a2,a3,a4,a5....an的两个排列b1,b2,b3,b4,b5...bn和c1,c2,c3,c4,c5...cn, 如果它们的前k（常数）项一样，且c(k 1)> b(k 1),则称排列c位于排列b（关于字典序）的后面。如1，2，3，4的字典序排在1，2，4，3的前面（k=2），1，3，2，4的字典序在1，2，3，4(k=1)的后面。下面列出1，2，3按字典序的排列结果：

　　1，2，3

　　1，3，2

　　2，1，3

　　2，3，1

　　3，1，2

　　3，2，1

　　（有些读者会发现它们手写排列的时候也不自觉得遵照着这个规则以妨漏写，对于计算机也一样，如果有这样习惯的读者的话，那它们的实际算法更适合于表达为下面要讲的算法。） 定义字典序的好处在于，排列变得有序了，而我们前面的递归算法的排列是无序的，由同一个序列生成的不同数组（排列）如1,2,3,4和2,3,4,1的输出结果的顺序是不同的，这样便没有统一性，而字典序则可以解决这个问题。很明显地，对于一个元素各不相同的元素集合，它的每个排列的字典序位置都不相同，有先有后。

　　接下来讲讲如何求某一个排列的紧邻着的后一个字典序。对证明不感兴趣的读者只要读下面

　　4/16页

　　加色的字即可。

　　定理：我们先来构造这样一个在它后面的字典序，再证明这是紧邻它的字典序。对于一个排列a1,a2,a3...an,如果a(n)> a(n-1)，那么a1,a2,a3...a(n),a(n-1)是它后面的字典序，否则，也就是a(n-1) > a(n),此时如果a(n-2) < a(n-1)，那么在a(n-1)和a(n)中选择比a(n-2)大的较小的那个数，和a(n-2)交换，显然，它也是原排列后面的字典序。更一般地，从a(n)开始不断向前找，直到找到a(m 1) > a(m)【如果a(n) a(2) > ...a(n)，是最大的字典序】，显然后面的序列满足a(m 1)>a(m 2)>...a(n).找到a(m 1)到a(n)中比a(m)大的最小的数，和a(m)交换，并把交换后的a(m 1)到a(n)按照从小到大排序，前m-1项保持不变，得到的显然也是原排列后面的字典序，这个字典序便是紧挨着排列的后一个字典序。

　　下面证明它是紧挨着的。1.如果还存在前m-1项和原排列相同并且也在原排列后面的字典序a1,a2,a3...bm,...，bm>原am，假设它在我们构造的字典序前面，那么必有bm < 交换后的am，但这是不可能的，因为am是后面序列中大于原来am的最小的一个，而bm必然又是后面序列中的大于am的一个元素，产生了矛盾。2.如果还存在前前m项和原排列相同并且也在原排列后面的字典序，它不可能在我们构造的字典序前面，因为我们对后面的数进行了升序排列，不存在比a(m 1)还小的数。3.如果还存在前k项（ka(k 1)[k 1 < m]对于我们构造的字典序也满足。证明完毕。

　　证明完成后，我们便可以通过上述的构造方法求得一个排列的下一个字典序排列了。

　　7.求下一个字典序排列算法：

　　bool Next_Permutation(int A[], int n)

　　{

　　int i,m,temp;

　　for(i = n-2;i >= 0;i--)

　　{

　　if(A[i 1] > A[i])

　　break;

　　}

　　if(i < 0)

　　return false;

　　m = i;

　　i ;

　　for(;i　　if(A[i] <= A[m])

　　{

　　i--;

　　break;

　　}

　　swap(A[i],A[m]);

　　5/16页