全排列算法解析(完整版)
全排列以及相关算法
在程序设计过程中，我们往往要对一个序列进行全排列或者对每一个排列进行分析。全排列算法便是用于产生全排列或者逐个构造全排列的方法。当然，全排列算法不仅仅止于全排列，对于普通的排列，或者组合的问题，也可以解决。本文主要通过对全排列以及相关算法的介绍和讲解、分析，让读者更好地了解这一方面的知识，主要涉及到的语言是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，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个元素的排列的算法：
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 { 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 是递归调用，对应的是第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,https://www.sodocs.net/doc/496449693.html,, 如果它们的前k（常数）项一样，且ck > bk,则称排列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的输出结果的顺序是不同的，这样便没有统一性，而字典序则可以解决这个问题。很明显地，对于一个元素各不相同的元素集合，它的每个排列的字典序位置都不相同，有先有后。 接下来讲讲如何求某一个排列的紧邻着的后一个字典序。对证明不感兴趣的读者只要读下面 加色的字即可。 定理：我们先来构造这样一个在它后面的字典序，再证明这是紧邻它的字典序。对于一个排列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) 下面证明它是紧挨着的。1.如果还存在前m-1项和原排列相同并且也在原排列后面的字典序a1,a2,a3...bm,...，bm>原am，假设它在我们构造的字典序前面，那么必有bm < 交换后的am，但这是不可能的，因为am是后面序列中大于原来am的最小的一个，而bm必然又是后面序列中的大于am的一个元素，产生了矛盾。2.如果还存在前前m项和原排列相同并且也在原排列后面的字典序，它不可能在我们构造的字典序前面，因为我们对后面的数进行了升序排列，不存在比a(m+1)还小的数。3.如果还存在前k项（k 证明完成后，我们便可以通过上述的构造方法求得一个排列的下一个字典序排列了。 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]); sort(A+m+1,A+n); Print(A); return true; } swap和Print函数读者可以自己写也可以参照我上面的写法，排序我这里直接使用了C++标准库中的sort，读者也可以自己写。有了这个算法后，我们便可以写一个非递归的列出全排列的方法，而且这个方法还带顺序： void Full_Array(int A[],int n) { sort(A,A+n); Print(A); while(Next_Permutation(A,n)); } 这个算法的时间复杂度为O(n^2 + n!*n) = O(n!*n)[前面是排序的复杂度，后面是遍历O（n!）乘以输出n]。这个算法还有一个好处，那便是它可以处理元素相同的情况，不会重复输出。（之前的算法会重复，而且要注意的是，这个算法判断句中的> 、<有没有=号都是确定的，不能改，否则出现处理相同元素时便会陷入死循环，具体的写法读者可以自己举例判断，看看怎样会进入死循环。如果要使之前递归的算法不重复，在交换之前要判断相邻着的两个数是否相同，如果相同，则不交换，比如和A[i]交换，要判断A[i]是否等于A[i+1]）。不过这个算法的缺陷是它把原来数组给改变了，读者可以自行在Next_Permutation当中使用int* Array = new int(sizeof(A);或者int* Array = malloc(sizeof(A)),然后把数组拷贝一遍，不对原数组进行处理，那么相应的全排列也要自己改写了，我这里就不写了。 8.C++ STL库中的next_permutation()函数：（#include 幸运的是，C++已经给我们提供了next_permutation模版函数，所以不用自己写，也就不用担心死循环的问题，不过这个函数没有输出，而是直接把数组变成了它的下一个字典序。下面给出它的源代码： // TEMPLATE FUNCTION next_permutation template bool next_permutation(_BI _F, _BI _L) { _BI _I = _L; //定义新的迭代器_I并将尾地址赋给它。 if (_F = = _L || _F = = --_I) //如果首地址等于尾地址或者等于尾地址小1，直接返回false return (false); //要注意是因为我们传递的是尾地址加1（A+n = A[n]的地址），这个判断主要是考虑边界问题。 for (; ; ) //死循环，用于找到a(m+1) < a(m). { _BI _Ip = _I; //定义迭代器_Ip并将_I赋给它。 if (*--_I < *_Ip) //这里在比较a(m+1)和a(m)的大小，没找到则到下一个循环。如果//找到，进入条件句，由于是用了--运算符，所以得到的实际上是_Ip，也即a(m)。 { _BI _J = _L; //定义新的迭代器_J并将尾地址赋给它，相当于从结尾开始//找。前面我的算法是从a(m+1)开始往后找，理论上从结尾开始找比较好，建议读者写的时//候也从结尾往前找。 for (; !(*_I < *--_J); ) //循环，直到找到_I<_J，由于是减减，所以得到了第一//个比_I大的元素。由于是从结尾开始找，所以加了"！"，和我的相反。 ;//仅仅为了找而找。。。 iter_swap(_I, _J);//a(m)和a(i)交换，相当于我写的swap语句，注意传递的是迭//代器，修改的是值。 reverse(_Ip, _L);//相比于我的全排序，直接把a(m+1)到a(n)反序更有效率。 return (true); //返回。 } if (_I = = _F) //判断是否到起点了，相应于m+1 = 2，则把刚才反过来的反回去，//再返回false { reverse(_F, _L); //有些读者喜欢在反序之前判断是否到起点，而实际上到起点的情况只有一种（最后一个），//不断地判断很浪费时间，还不如在最后再反回来。 return (false); } } } 它的第一个参数是迭代器（指针、数组）的首地址，第二个参数是末地址，可以这样传递：next_permutation(A,A+n)来获得整个数组的下个字典序。我在上面已经写了完整的解释，大家可以对比我的算法和C++标准库里的算法，当然大家可以明显看到标准库算法的优越性，大家可以照着上面的解释自己写一个，不用全一样，模式一样即可，它的算法是最高效的（要不怎么能当模板？）。当然，标准库的算法为了使效率最快，安全性最高，总是喜欢用一些++啊--啊之类的运算符使得代码难读，读者在这方面可以不用模仿，算法上模仿就成了。下面再补充一些：在库中还有一个可以增加比较器的模版函数，不过实际上这个函数也不善于处理大型数据，有兴趣可以用。在C++标准库中还提供了找上一个字典序的算法， perv_permutation()，用法一样，下面我附上原码，就不解释了，原理差不多，有兴趣的读者可以自己读读或者自己写一个。 // TEMPLATE FUNCTION prev_permutation template bool prev_permutation(_BI _F, _BI _L) {_BI _I = _L; if (_F == _L || _F == --_I) return (false); for (; ; ) {_BI _Ip = _I; if (!(*--_I < *_Ip)) {_BI _J = _L; for (; *_I < *--_J; ) ; iter_swap(_I, _J); reverse(_Ip, _L); return (true ); } if (_I == _F) {reverse(_F, _L); return (false ); }}} 9.字典序的中介数，由中介数求序号： 这里我要引入一个新的概念：中介数。为什么要引入这么一个概念呢？很多时候，我们要通过一个排列得出它的字典序中的位置（序号），比如1234567应该排在第0位（开始位），1234576应该排在第1位，7654321排在第7！-1 = 5039位。当然，我们可以通过计算 Next_Permutation 函数的迭代次数来得到这个数据，但这样时间复杂度最差为O （n!），是非常不划算的，因为我们仅仅要求一个数的位置。所以我们要先从数学的角度去计算这个问题。 3456721排在第几位？ 1.先看看首位3，在以3开头的数前面有以2开头和以1开头的数，这些数的个数为2*6!个，其中2代表1和2两个数。 2.再看看第二位4。如果已经确定由3开头，那么在4开头前面的数有几种呢？也是以2开头的数和以1开头的所有数，因为3已经放在开头，所以这里不算，这些数的个数为2*5！。 3.再往下看，第三位5.如果已经确定34开头，在5开头前面的有几种呢？由于3、4已经放在前面，这里还是只有1、2.这些数的个数为2*4！。 4.345已经确定，再6开头的前面有2*3！，再7开头前面有2*2！，在2开头前面有1*1！个（因为只剩1了）,在1开头前面的没有了。（0*0！） 于是我们得到在3456721前面的数有2*6！+ 2*5！+ 2*4！+2*3！+2*2！+1*1 = 1745位。也说是说，在3456721前面的数一共有1745位，由于我们是从0开始的，所以它的位置也就是1745位。 上述计算过程对应了相应的算法：从高位往低位看，或者对于数组而言从序号小的往大的看，按照3，4，5，6，7，2，1[a[0],a[1],a[2],a[3],a[4],a[5],a[6]]的顺序，看它的右边比它小的数的个数k[1],k[2],k[3]...（因为左边的数已经确定了），每一位的k[i]*[(n-i-1)]! [此处n = 7]乘以它所在的位数-1的阶乘，比如3在第7位（在数组中是第0位，所以用n-0），减1得到后面还剩6位，而k[0]为2，因为在3的右边比3小的数只有两个。其它的位依次类推。为了简化公式，我们一般取i=为数组序号加1（即a[0]我们认为是a[1],用来和实际意义相近，因为我们实际中第一个数都是1而不是C 语言中的0）。得到公式： n-1 ∑k[i](n-i)! i=1 其中i 为数组的序号，从1开始，实际写算法时应从0开始，n 为数组元素的个数，k[i]表示第i 个元素的右边（从第i+1个元素开始到数组末尾）比第i 个元素小的元素的个数。 有了上述公式，就可以方便的计算一个排列在字典序中的位置了。比如7654321 = 6 * 6！+ 5 * 5！ + 4 * 4! + 3 *3! + 2*2! + 1*1! = 5039. 到此，我们给出字典序中介数的定义： 定义：由上述算法给出的数组k[i]按照顺序排列所形成的数]1[]...4[]3[]2[]1[ n k k k k k 叫做这个排列的字典序中介数。如7654321的中介数为654321,3456721的中介数为222221。中介数之所以称为中介数，是因为我们知道一个排列的中介数后，便可以很方便得求得它在字典序中的序号，而这个数在实际上没有明确的意义，所以称为中介数，要注意的是，中介数 比原来排列的位数（数组的元素个数）少一位，因为最后一位的结果必然是0。读者应多多练习求一个排列的中介数以及相应的序号。以上算法的时间复杂度为)(2n O ，其中求中介数为)(2n O ，由中介数到序号为O （n ）。这个算法比初始的想法的O(n!)要好的多。这个算法实际的代码我就不写了，读者可以自己写，这要是掌握这个算法的原理和过程。这里还要说的是这个算法不适合于有重复数字的情况，下面所讲的所有算法均不适合（可以想想为什么）。 10.由中介数求排列： 通过中介数可以很方便地求序号，而通过一个排列可以很方便地得到它的中介数，那么自然要想到另一个过程：通过中介数能否很方便地反推回排列呢？首先，显然地，中介数和排列是一一对应的，不存在一个中介数对应多个排列的情况（读者可以想想为什么）。所以，必然有办法可以求回去。按照我的习惯，还是从基本的想法做起，我们是怎样求得中介数的，由此反推回如何求排列。比如222221。乍一看似乎很难入手，正如微分容易而积分难一样，当然，这个逆过程比积分要简单的多，因为我们已经确定它是唯一的。 方法：从最左边开始推算：2开头，证明最高位的右边比它小的数只有两个，马上可以得到最高位是3.第二位也是2，因为3已经有了，那么还有比它小的两个数，那就是4了，以此类推，我们可以很方便地求得一个中介数的原排列。方法即从最左边推算。这是一个逆过程，最初看看是个不错的想法，做出来也比较快，而实际上不是这样的。我们看看我们实际的运算过程：最左边的数如果是x1，那么它的原排列位是x1+1，当我们去看第二个数时，我们先假想它是x2+1，如果第一个排列位比x2+1来得大，那么没有问题，如果比它小或者相等，则要加上1，所以实际上，我们每求一位数，都要先让它和前面的所有数进行比较来获得它的定位。求解中介数还有一些类似的方法，这里我便不罗列了，反正大同小异，表面上看起来比较简单，但实际实现起来是比较复杂的（由其是对计算机而言）。而且，在这种方法中，我们很难通过已知的排列序号反推出原来的排列，所以有必要给出新的中介数形式。 11.递增进位制数法： 为了改变由中介数求原排列的复杂性，我们要修改我们定义中介数的方法，我们的中介数是和相应的位数相关联的，中介数的下标对应了位的下标。我们定义一种新的中介数，称为递增进位制数，它的下标对应了数字大小（为了简便，下面还是叫做中介数，为了区分，我们把原来的中介数叫作初始中介数）。我们看一个新的数：3647521.它的初始中介数是242321（读者应该已经会求了），我们不按照从左到右的顺序排，而是按照数字的大小来排，3对应的是2，因为是原排列位上的数是3，所以把它放在第3位；6对应的是4，因为原排列位上的是6，所以把它放在第6位，4对应的是2，放在第4位，7对应3，放在第7位，5对应2，放在第5位，2对应1，放在第2位，1对应的是0，我们没有写出来。我们得到342221(0).相当于对初始中介数进行了排序，按照原来位上数字的大小排序，这样的数称为递增进位制数。读者可能还看不出来这个数和递增进位制这个名词有任何关系，它只是从中介数演变过来而已。实际上，经过这样的一个演变，每一位上的数都不会超过位的大小，比如第4位上的2（我用蓝色记号的），它是不能达到4的，因为第4位对应原排列上的4，而原排列上的4产生的初始中介数位是不可能大于4的（因为初始中介数是它右边比它小的数的个数，原排列是4，不可能有5个比它小的数）。所以就形成了递增进位制数。它的第一位恒为0，（所以用括号把0括号起来了），是个一进制数，第二位为1或0，是个二进制数，第三位为2或1或0，是个三进制数，以此类推。为了便于读者理解，我给出这样一个数的运算： 342221 (0)+ 1 = 342221 + 1（因为一进制数加任何数都相当于把它进位）= 342300.因为第二 位是个二进制数，1+1进位了，第二位为0，第三位是个3进制数，2+1还是进位了，第三位为0，第四位是个四进制数，没有进位，所以为3.得到342300。和字典序一样，对中介数加1后相当于对应的序号也加1.这个过程也不是很难，原理还是加法，只是每一位的进制都不相同，当然，如果做一个比较复杂的运算就比较难了。读者可以自己练习几个。由这样的中介数求它的序号的方法为 (((((k[1]*(n-1) + k[2])*(n-2)+k[3])*(n-3)..*2 + k[n-1].)，其中k[i]就是新的中介数，i从1开始表示从左往右数，即数组的序号（对应n -i + 1位）。这里的n表示的是原排列的元素个数。 实际上就是一种奇特的进制，要注意的是，此时的序号并不是按照字典序排序的，而是一个新的排序方式。1234576 新的中介数：100000。序号：720而不是原来的1。但是范围是一样的，而且始末点是一样的。1234567 ->0 7654321->5039(读者自己算一下)。讲了这么多，读者可能觉得这个方法看着非常麻烦，它到底哪里有利于求原排列呢？下面就讲它确定原排列的方法：数空格法。 __ __ __ __ __ __ __我们画这样七个空格，来求342221的原排列：第7位数字是3，我们从右向左数3个空格，再往前数一个空格，空格中填入对应的位数7，把对应的空格擦除。 __ __ __ 7 __ __ __。第6位数字是4，我们从右向左数4个空格，其中已经放上数的不算空格，再往前数一个空格，空格中填入6，把对应空格擦除。 __ 6 __ 7 __ __ __。接下来的步骤也是一样的，第5位的数字是2，数2个空格，再往前数一个空格填入5。 __ 6 __ 7 5 __ __。第4位是2，数2个空格再往前数一个空格填入4。 __ 6 4 7 5 __ __。第3位是2，数2个空格再往前数一个空格填入3. 3 6 4 7 5 __ __。第2位是1，数1个空格，再往前数一个空格填入2. 3 6 4 7 5 2 __。第1位是0，数0个空格，再往前数一个空格填入1. 3 6 4 7 5 2 1.由此，我们得到了原来的排列3 6 4 7 5 2 1。可以看到，整个过程都是确定的，不需要进行额外的比较，相比于原来的中介数要简便得多，而且得到中介数的方法也基本类似，虽然它的本质是一个递增进制数可能有些困扰，如果不去管它的本质，则是以下简单的事情： 1.用原排列求新的中介序。 2.用中介序方便得求得原排列，使用空格法。 3.用中介序的一个公式求得新的序号。 接着还要讲讲递增中介数的最后一个好处，那便是可以方便得通过序号求回中介数。对于字典序来说，它是由几个阶乘相加得到的，反推回中介数基本上是不可能的（或者说是比较麻烦的），而对于递增进制中介数，这个过程非常的简单。通过上面的公式，我们很容易得到相逆的公式：记序号为m. m = m1*1 + k[n]; k[n]是一进制，恒为0. m1 = m2 * 2 + k[n-1]; 由进制的关系知道k[n-1]是二进制的0<=k[n-1]<=1 m2 = m3 * 3 + k[n-2]; 由进制的关系知道k[n-1]是三进制的0<=k[n-1]<=2 ... m(n-2) = m(n-1) * (n-1)+k[2]; 0<=k[2]<=n-2; m(n-1) = k[1]; 得到序号后，除以2取余得到k[n-1],商接着除以3取余得k[n-2]，以此类推得到原中介数。由于递增进位制数法可以在原排列、中介数、序号之间进行较为方便的转换，我们可以从0开始递增中介数，进而转换为原排列并不断地求下一个序列，也可以得到全排列的算法。 不过这里我就不写了，读者有兴趣可以写写。 12.递减进位制数法： 考虑到递增进制法中由于最低位是二进制，而且低位的进制都比较低，在求下一个排列时，中介数加1往往会导致很多的进位，计算比较麻烦，所以有了递减进位，实际上就是将递增进位制的中介数倒过来即可。如342221变成122243.求序号时的公式记住也是倒过来。((((k[1]*3) + k[2])*4+k[3])*5..k[n-2]*n + k[n-1]，其中k[i]就是递减进制中介数，i 从1开始表示从左往右数，即数组的序号（对应n -i + 1位）。这里的n表示的是原排列的元素个数。 如122243表示为（（（（1*3+2）*4+2）*5+2）*6+4）*7+3 = 4735. 由于低位都是比较高的进制，所以不容易产生进位，求下一个排列非常地简单。 我们看这个例子：122243 + 1 = 122244.这里我们不需要再进位，而是很方便的计算。122244对应的序号是4736.反过来求出原排列的方法也很简单，先反序得到递增中介数再运算即可。122244 = 442221(反序) = __ __ __ __ __ __ __ = __ __ 7 __ __ __ __ = __ 6 7__ __ __ __ = __ 6 7 __ 5__ __ = __ 6 7 4 5 __ __ = 3 6 7 4 5 2 1.（读者可以自行练习空格法） 和原来的122243对应的排列3 6 4 7 5 2 1相对比，发现仅仅是4和7交换了位置。我们可以再看看122244 +1 = 122245 = 542221（反序）= __ __ __ __ __ __ __ = __ 7 __ __ __ __ __ = __ 7 6 __ __ __ __ = __ 7 6 __ 5 __ __ = __ 7 6 4 5 __ __ = 3 7 6 4 5 2 1. 我们可以发现它仅 仅是上一个排列的6和7交换了位置。读者可能发现，如果再加两次，就会有进位，此时排列又更替了。所以，实际上，递减进位制数法的排序采用的就是这种两个相邻元素交换的方式，并且是从右往左单向交换（至于它的数学原理这里就不深究了，有兴趣的读者可以研究一下）。通过递减进位制法也可以得到全排列的算法，相比于递增进位制法较简单。13.邻位对换法： 我们从递减进制数法从得到启示，递减进制法中的交换是单向的，这导致交换到头是排列会发生更替，如果我们采用双向的交换，便可以不断地交换下去，于是产生了邻位对换法。邻位对换法在找下一个排列的方法上在很多情况下要比字典序算法要快上许多，因为每次的下一个排列只是交换两个相邻的元素，当然缺点是有到左端或者右端时要进行找最大可移动数的弊端，整体上速度和字面序算法差不多。 当然，读者可能还没有理解邻位对换法的概念，下面开始讲解。在讲解之前先介绍数学中的两个概念，不过其实在这节里没有用，下面一节才用到。 定义1：在一个序列中任意两个元素对如果满足a[k] < a[m](k < m)，则称为正序，否则称为逆序。 定义2：如果一个排列中逆序的数目为奇数，则称为奇排列，若为偶数则称为偶排列。 初始的时候，我们假设这个序列是一个升序的序列，而且最小元素至少为1，升序的序列总是偶排列，并且我们设定初始所有数的移动（其实就是交换）的方向均从右向左。 我们给出可移动的概念：如果一个数沿着它的方向的邻位比它小，则称这个数是可移动的。由这个概念可以知道，1是永远不可移动的，最大的数除非是在两端而且方向指向序列外面，要不一直是可移动的。 我们再规定一个性质：如果一个可移动的数发生了移动，那么比它大的所有数的方向都反过来。对于一个排列而言，它的邻位对换法的下一个排列是最大的可移动的数移动后的结果。 我们看一个例子： 1，2，3，4.[很显然，这是一个偶排列，因为它是升序序列。1<2,2<3,3<4,都是正序]。为了得到下一个排列，我们取最大的数4，它是最大的可移动数，并把它向左移动： 1，2，4，3.实际上是3和4的交换，这便是它的下一个排列。再移动： 1，4，2，3.再移动， 4，1，2，3. 由此我们得到了四个排列，每次都是通过交换相邻元素实现的。当4到头了之后，无法移动了，此时我们找到可移动的最大的数3，并把它向左移动1次，得到 4，1，3，2. 此时由于4的移动方向已经反过来了，所以最大可移动数为4，把4依次向右移动： 1，4，3，2 1，3，4，2 1，3，2，4. 4到了头，再次无法移动了，此时最大的可移动的数变成了3，把3向左移动一次，得到3，1，2，4. 此时4的移动方向再反过来向左，得到 3，1，4，2. 3，4，1，2. 4，3，1，2. 此时3也到头了，此时我们找可移动的最大的数，2.得到 4，3，2，1. 4和3的移动方向再反向右， 3，4，2，1 3，2，4，1 3，2，1，4. 4到头后，由于此时3的移动方向向右，得到 2，3，1，4. 则4的方向又反，向左移动 2，3，4，1 2，4，3，1. 4，2，3，1. 此时3再向右移动，得到 4，2，1，3. 此时4再向右移动 2，4，1，3. 2，1，4，3. 2，1，3，4. 由此，我们从一个升序排列得到了全排列。通过这个例子，读者应该可以大概了解邻位对换法的基本过程了： 1.找到最大可移动数并移动至端点 2.找到现存的最大可移动数移动一次 3.回到原最大可移动数并移动至另一端点 4.找到现存的最大可移动数移动一次 ...... 5.找不到最大可移动数，循环结束，遍历结束。 由这个过程也可以直接得到一个非递归的算法，首先我们要写一个找到最大可移动数并移动一次的方法： bool Movable(int A[],direct[],int n) //direct参数用于接收每个元素移动方向的数组。 { int max = 1;//初始化最大可移动数为1，因为规定1是最小的数，可以自己设定。 int pos = -1;//初始化最大可移动数的位置为-1. /*下面先找到最大可移动数位置*/ for(int i=0;i { if(a[i] < max) continue; if((i < n-1 && a[i] > a[i+1] && direct[i]) || (i > 0 && a[i] >a[i-1] && ! direct[i])) { max = a[i]; Pos = i; } } /*下面对它进行移动*/ if(pos = = -1) return false; if(p[pos]) { swap(A[pos],A[pos+1]); swap(direct[pos],direct[pos+1]);//我这里用同样名字了，可以写模版，也可以改函//数名字 } else { swap(A[pos],A[pos-1]); swap(direct[pos],direct[pos-1]);//我这里用同样名字了，可以写模版，也可以改函//数名字 } /*最后调整所有比最大可移动数大的数的方向*/ for(int i = 0;i { if(A[i] > max) direct[i] = !direct[i]; } return true; } 有了这个方法后，便可以进行全排列了。 17.邻位对换法全排列： void Full_Array(int A[], int n) { bool* direct = new bool[n]; //产生一个记录每个元素移动方向的数组 sort(A,A+n); //将原序列变成一个升序 for(int i=0;i direct[i] = false; //初始化移动方向为false，表示从右向左。 do { Print(A,n); if(A[n-1] = = n) for(int i=n-1;i>0;i--) { swap(A[i],A[i-1]); swap(direct[i],direct[i-1]); //我这里用同样名字了，可以写模版，也可以改函//数名字 Print(A,n); } else for(int i=0;i < n; i++) { swap(A[i],A[i+1]); swap(direct[i],direct[i+1]); //我这里用同样名字了，可以写模版，也可以改函//数名字 Print(A,n); } }while(Movable(A,direct,n)); delete []direct; } 15.邻位对换法的下一个排列： 为了让读者更容易理解和掌握邻位对换法的基本过程，我先通过一个例子让大家了解如何去得到下一个排列，并接着给出了相应的算法，但是，如果我们得到了一个排列比如： 2，3，4，1.我们仅仅知道通过一次邻位交换可以得到它的下一个排列，但是是哪一位的交换呢？ 首先，我们得找到最大的数的位置。2，3，4，1.中最大的数位于第3个位置。位置是好找的，那方向如何判断呢？ 我们接着要判断最大的数此时的移动方向。之前给出了奇排列和偶排列的概念，在这里便用的上了。每当我们的最大的数从一端移到另一端时，就要进行最大可移动数的交换，这个过程过后，在不考虑最大数的数列中便会增加一个逆序。而初始的1，2，3的逆序为0，最大的数在移动的过程中不会改变除去最大数后的数列的顺序，所以，不考虑最大数后的数列的逆序为偶数个时（偶排列），最大数在向左移动，逆序为奇数个时（奇排列），最大数向右移动。2，3，4，1中不考虑最大数的序列2，3，1的逆序为1，所以4在向右移动。同样地，如果最大数此时在某一端点，我们可以通过上述性质判断是移动最大数还是找到最大可移动数并进行交换。当然这里我们还有问题没有解决：如何判断非最大数的数此时的方向呢？如果无法判断这个，还是无法找到下一个排列。 与上面类似地，我们可以得到更一般的结论：一个非最大数的方向由所有比它小的数构成的序列的逆序决定的，如果是偶数个时，向左，奇数个时向右[也即的所有的数包括最大数都满足这条规则]。 2，3，4，1中容易知道此时3是向右的，2是向左的，4是向左的，1是不动的。读者可以自己对1，2，3，4这个全排列的每一个进行练习。 16.邻位对换法的中介数： 邻位对换法的中介数也不难求。对于某个排列如2341，，从1开始看起（1没有方向，不用算），如果它是向左的，则右边所有比它小的数的个数为中介数的最高位，如果是向右的，则左边所有比它小的数的个数为中介数的最高位，位逐次降低，如2对应k[1] = 1，最高位为1，3对应k[2] = 1，第三位为1，4是向左的，第二位为k[3] = 1. 得到111为2341的中介数。 对应的序号的求法为 (1 * 3 + 1) * 4 + 2 = 17，和递减进位的公式一样，所以通过序号求中介数也是和递减进位、递增进位类似，除以n取余，除以n-1除余，。。。。。。 邻位对换法由中介数求原排列的方法似乎也不是很简单，读者就不用掌握了，这里就概括一下：首先要判断最大数的方向，这个和上面一样，要由其它数构成的序列的奇偶性决定，所以要求其它数构成序列的奇偶性，这个奇偶性通过求序号的公式来得到，由性质原排列中取所有小于等于k的数构成的数列（顺序不变）的奇偶性和对应的序号的奇偶性相同。我举简单的例子：2341的中介数为112.那么231的中介数为11（舍掉低相应位数即可得到相应的中介数），则它的序号为1*3+1 = 4是偶数，所以最高位的方向4的方向向左。以此类推即可。 17.组合数的字典序与生成： 最后我们讲讲组合数的生成。首先我们看看列出集合的所有子集、要列出一个集合{1,2,3,4}的所有子集是很容易的，我们可以按照二进制数的顺序，0000，0001，0010，0011，0100，0101，0110，0111......来表示我们要取的元素，其中0表示不取，1表示取，这样就获得了一个顺序。而组合也包含在这个顺序当中。我们看从{1,2,3,4}中选取两个元素的所有组合：0000 0001 0010 0011 0100 01010110 0111 1000 1001 1010 1011 1100 1101 1110 1111. 蓝色标记的是我们所取的组合。对应的顺序便是｛3，4｝｛2，4｝｛2，3｝｛1，4｝｛1，3｝｛1，2｝我们可以用字典序对这些组合进行排序：{1,2}{1,3}{1,4}{2,3}{2,4}{3,4}.共6种。按照我的习惯，我们先看看我们平常列举组合数所采取的策略。比如说1，2，3，4，5取3个元素的组合。我们先从小的取：1，2，3.再把最后一个数改变:1,2,4;1,2,5.当到达5之后，含有1，2的所有组合已经被罗列完了。改变2为3，1，3，4；1，3，5；此时我们不能再选择2进行罗列，否则会重复。改变3为4，此时2和3都不能放入，1，4，5.改变4为5时，2，3，4都不能放入，不存在组合了。这时改变1为2。之后不能再选择1罗列。所以，对于一个组合C1C2C3C4...Cr(每个代表一个数，一共r个数，代表一个组合，数从[1,n]中选)，由于一个组合自身是不讲顺序的，我们可以对组合进行升序排列，使得C1 C(r - m)到达n - m后就不能再递增上去。由k = r - (r - k)得到 C(k)到达n - (r - k) = n - r + k 后就不能再递增上去。 那么，对于C1C2C3C4...Cr，我们从Cr开始向前找，直到找到有Ci < n - r + i，并执行 Ci = Ci + 1。由于所有的组合都已经强制升序，所以Cj = Ci + (j-i),j = i+1,i+2,...r即它后面 的每一项都比前一项大1。由于Ci < n -r + i，Cr = Ci + (r - i) <=n(因为Ci比原来大了1)，所以构造出来的新的C1C2C3C4...Cr仍是[1,n]中选r个元素的一个组合，而且显然它在原组合的字典序后。由此，我们构造出了一个排在原组合的字典序后面的组合。接下来证明它是紧邻着原组合的。 证明：假设有一个组合B1B2B3B4...Br的前i-1个元素和C1C2C3C4...Cr一样，且在原组合字典序后，在我们构造的字典序前，那么必有新Ci > Bi > 原Ci，这是不可能的，因为新Ci = 原Ci + 1。同样不可能存在前i个元素一样但在新Ci字典序前的组合，因为强制排序后Cj 到Cr 的每个元素都是最小的。同样不可能存在前k个元素一样（k < i）但在新Ci字典序前的组合。 如果找不到有Ci < n - r + i，说明已经到达最后一个：n -r + 1,n - r + 2,...n.由此我们可以直接得到组合数的相对字典序，下一个组合的算法： bool Next_Combination(int A[],int n,int r) { int i; sort(A,A +r); for(i = r- 1;!(A[i] < n - r + i) && i > 0;i--); if (i = = 0) return false; A[i] = A[i] + 1; for(int j=i+1;j A[j] = A[i] + j - i; return true; } 当然，这个算法中的组合是从1到n中选取的。读者可以通过给自己写选取的组合规定序号进行选取，也可以自行修改算法。 —————by 夜せ︱深 排列组合n选m，组合算法——0-1转换算法（巧妙算法）C++实现 知识储备 排列的定义：从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 A(n,m）表示计算公式： 注意：m中取n个数，按照一定顺序排列出来，排列是有顺序的，就算已经出现过一次的几个数。只要顺序不同，就能得出一个排列的组合，例如1,2,3和1,3,2是两个组合。 组合的定义：从n个不同元素中，任取m(m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 表示。 计算公式： 注意：m中取n个数，将他们组合在一起，并且顺序不用管，1,2,3和1,3,2其实是一个组合。只要组合里面数不同即可 组合算法 本算法的思路是开两个数组，一个index[n]数组，其下标0~n-1表示1到n个数，1代表的数被选中，为0则没选中。value[n]数组表示组合 的数值，作为输出之用。 ? 首先初始化，将index数组前m个元素置1，表示第一个组合为前m 个数,后面的置为0。? 然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为?“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。一起得到下一个组合（是一起得出，是一起得出，是一起得出）重复1、2步骤，当第一个“1”移动到数组的n-m的位置，即m个“1”全部移动到最右端时；即直到无法找到”10”组合,就得到了最后一个组合。 组合的个数为： 例如求5中选3的组合： 1 1 1 0 0 --1,2,3? 1 1 0 1 0 --1,2,4? 1 0 1 1 0 --1,3,4? 0 1 1 1 0 --2,3,4? 1 1 0 0 1 --1,2,5? 1 0 1 0 1 --1,3,5? 0 1 1 0 1 --2,3,5? 1 0 0 1 1 --1,4,5? 0 1 0 1 1 --2,4,5? 0 0 1 1 1 --3,4,5 代码如下： 第一章算法概述 1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。 2.算法的性质： 1)输入：有零个或多个输入 2)输出：有至少一个输出 3)确定性：每条指令是清晰的、无歧义的 4)有限性：每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复 杂性，需要空间资源的量称为空间复杂性 2)三种时间复杂性：最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念：直接或间接调用自身的算法 2.递归函数：用函数自身给出定义的函数 3.递归要素：边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout< 字符串的排列组合算法合集 全排列在笔试面试中很热门，因为它难度适中，既可以考察递归实现，又能进一步考察非递归的实现，便于区分出考生的水平。所以在百度和迅雷的校园招聘以及程序员和软件设计师的考试中都考到了，因此本文对全排列作下总结帮助大家更好的学习和理解。对本文有任何补充之处，欢迎大家指出。 首先来看看题目是如何要求的（百度迅雷校招笔试题）。一、字符串的排列 用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列,如 abc 的全排列: abc, acb, bca, dac, cab, cba 一、全排列的递归实现 为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后，递归的代码就很容易写出来了： view plaincopy #includeiostream?using?namespace?std;?#includeassert.h?v oid?Permutation(char*?pStr,?char*?pBegin)?{?assert(pStr?pBe gin);?if(*pBegin?==?'0')?printf("%s",pStr);?else?{?for(char *?pCh?=?pBegin;?*pCh?!=?'0';?pCh++)?{?swap(*pBegin,*pCh);?P ermutation(pStr,?pBegin+1);?swap(*pBegin,*pCh);?}?}?}?int?m ain(void)?{?char?str[]?=?"abc";?Permutation(str,str);?retur n?0;?}? 另外一种写法： view plaincopy --k表示当前选取到第几个数，m表示共有多少个数?void?Permutation(char*?pStr,int?k,int?m)?{?assert(pStr); ?if(k?==?m)?{?static?int?num?=?1;?--局部静态变量，用来统计全排列的个数?printf("第%d个排列t%s",num++,pStr);?}?else?{?for(int?i?=?k;?i?=?m;?i++)?{?swa p(*(pStr+k),*(pStr+i));?Permutation(pStr,?k?+?1?,?m);?swap( *(pStr+k),*(pStr+i));?}?}?}?int?main(void)?{?char?str[]?=?" abc";?Permutation(str?,?0?,?strlen(str)-1);?return?0;?}? 如果字符串中有重复字符的话，上面的那个方法肯定不会符合要求的，因此现在要想办法来去掉重复的数列。二、去掉重复的全排列的递归实现 由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122，第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了，但对212，它第二个数 小学生查字典口诀 学查字典并不难，偏旁部首看端详。 没有部首查起笔，形声字儿查形旁； 头底两层是部首，要让字头当偏旁； 左右两边是部首，取左去右有保障； 内心外壳是部首，舍去里边查外框； 整个字儿是部首，此字本身是偏旁； 一字头上生“二角”，取其下底把“角”砍； 下底如果不成部，左上角当此字旁； 有些生字较特殊，顶天立地当偏旁； 多查多想抓规律，相同部首不能忘。 查字典常用的三种方法是： 音序查字法、部首查字法和数笔画查字法。 ?如果很容易确定部首，但不确定读音就可以用部首查字法；?如果知道读音，但不会写这个字，就用音序查字法； ?如果是独体字就用数笔画查字法。 字、词典是无声的老师，这位老师随时会帮你解决疑难，扫除 学习中的“拦路虎”。你会只花少量的时间，非常方便地得到 较多、较全面、较准确的知识。熟练查字、词典，首先要学会 检字。下边以《新华字典》为例介绍这几种查字法。 一、音序查字法 音序检字法是按字音查字词的一种方法。很多字典或词典是按汉语拼音字母的顺序编排的。根据一个字的汉语拼音第一个字母，就可以在“汉语拼音音节表”中找到这个字的拼音音节在正文中的页码，再按照这个字的声调到那一页中去找。凡是要查只知道读音而不知道写法或意义的字，都可以用这种方法，但必须熟悉汉语拼音字母顺序和汉语拼音音节。 运用条件： ①字音要读得正确； ②准确无误地了解这个字的声母、韵母； ③掌握字母的写法。 知道了这个字的读音，不知道它的写法，或不知道它的意思， 就必须运用音序查字法查字。 查字步骤： ①确定音部。按要查字的读音确定音节的第一个字母——音部。 ②查音节索引。在《汉语拼音音节索引》中所确定的音部栏里，找出要查字的音节，并看准该音节后面所标的正文页码。 ③翻阅正文。按页码翻阅正文，找出要查的字。 在学习中遇到不理解的字或不会写的字，只要能读准字音，就可以运用音序检字法去查检。 下面的歌诀，可以帮助同们掌握这种检字法： 音序检字须认真，读准字音很要紧。 打头字母定音部，再找音节看《索引》； 按照例字找同音，对照页码翻正文； 根据声调找汉字，字形字义记在心。 部首检字法：部首检字法属于按形查字中的一种方法。它是根据汉字的部首去查检的。凡字典正文中的单字是按部首归类进行排列的，都可以运用部首检字。 部首检字的基本步骤? ⑴确定出部首。先对所要查的字确定出查什么部。 ⑵查《部首目录》。在《部首目录》中查出该部首在《检字表》中的页码。 ⑶查《检字表》。按照页码在《检字表》中这个字的余画（即除去部首还余几画）里查出这个字在字典正文中的页码。 全排列的生成算法对于给左的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。字典序法按照字典序求下一个排列的算法广例字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是：123,132,213,231,312,321o注意一个全排列可看做一个字符串，字符串可有前缀、后缀/生成给泄全排列的下一个排列所谓一个全排列的下一个排列就是这一个排列与下一个排列之间没有其他的排列。这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。广例839647521是1—9的排列。1—9的排列最前而的是123456789,最后而的是987654321,从右向左扫描若都是增的，就到了987654321,也就没有下一个了。否则找出第一次出现下降的位置。算法：由P1P2...Pn生成的下一个排列的算法如下：1求j=max{j| Pj-I 第2次课枚举法中的字典排列 小热身 体会一下，“分给两个人”和“分成两堆”有什么区别呢？ (1)把5个苹果全部分给两个人，共有多少种不同的分法？ (2)把5个苹果分成两堆，共有多少种不同的分法？ 例题1:卡莉娅、墨莫、小高三个人去游乐园玩，三人在藏宝屋中一共发现了4件宝物，三人找到的宝物数量共有多少种不同的可能？(可能有人没有发现宝物) 练习1:老师准备了6个笔记本奖励萱萱、小高、墨莫三人，每人至少得到1本笔记本，请问:老师有多少种不同的奖励方法？ 例题2:老师要求每个同学写出3个自然数，并且要求这3个数的和是8。如果两个同学写出的3个自然数相同，只是顺序不一样，则算是同一种写法。试问:同学们最多能得出多少种不同的写法？ 练习2:三个大于0的整数之和(数与数可以相同)等于10，共有多少组这样的三个数？ 例题3:如下图所示，有7个按键，上面分别写着1、2、3、4、5、6、7这七个数字。请问: (1)从中选出2个按键，使它们上面的数字的差等于2，一共有多少种选法？ (2)从中选出2个按键，使它们上面的数字的和大于9，一共有多少种选法？ 练习3:有一次，著名的探险家大米得到一个宝箱，但是宝箱有密码锁，密码锁下面有一行小字，密码是和大于11的两个数，而且这两个数不能相同，不用考虑数的先后顺序，你知道密码共有多少种可能吗？ 例题4:如图，数一数图中包含星星的长方形(包括正方形)有多少个？ 练习4:如图，数一数图中包含星星的正方形有多少个？ 作业: 1、有4支完全相同的铅笔要分给3位同学，每位同学至少分1支，共有多少种不同的分法？ 2、有面值分别为1元、10元和50元的纸币若干，每种面值的纸币张数都大于 3、如果从中任意取3张，那么能组成的钱数共有多少种？ 3、从1、2、3、 4、 5、6这六个数字中选出2个数字，使它们的数字的差等于2，一共有多少种选法？ 4、数一数，下图包含星星的长方形(包括正方形)有多少个？ 5、在下图中，一共能找出多少个含“☆”的三角形。 字符串全排列算法C语言实现 问题描述： 输入一个字符串，打印出该字符串中字符的所有排列。 输入: 123 输出: 123 132 213 231 312 321 问题分析： 现象分析： 这种问题，从直观感觉就是用递归方法来实现即：把复杂问题逐渐简单化，进而得出具体代码实现。（如何发现一个问题可以使用递归方式来解决？经分析可以发现：M 个数的排列方法与N(N>M)个数的排列方法没有区别，处理方法与数据的个数没有关系。 处理方法的一致性，就可以采用递归）。 3个数（123）排列，第一位1不动，剩下两个数（23）的排列，只要相互颠倒一下，就可以出现关于1开头的所有排列 123 132 把2换到第一位，保持不动，剩下的两个数（13）的排列，只要相互颠倒一下，就可以出现关于2开头的所有排列 213 231 同理，把3换到第一位，可得到 312 321 扩展： 把3个数的所有排列，前面加一个4，就可以得到关于4开头的所有的排列4123 4132 4213 4231 4312 4321 若把4与后续数据中的任意一个数据交换，通过完成对后续三个数的全排列，就可以得到相应的数开头的四数的排列。 总结： 对4个数的排列，可以转换成首位不动，完成对3个数的排列 对3个数的排列，可以转换成首位不动，完成对2个数的排列 对2个数的排列，可以转换成首位不动，完成对1个数的排列 对于1个数，无排列，直接输出结果 算法实现说明： 对n个数的排列，分成两步： （1）首位不动，完成对n-1个数的排列， （2）循环将后续其他数换到首位，再次进行n-1个数的排列 注：排列完成后，最终的串要与原串相同 C语言代码实现： #include 算法设计与分析期末综合实验试题清单 分治与递归 1-1 合并排序 问题描述：给定n 个整数，利用合并排序思想将其调整成单调序列。 输入：整数的个数n ，以及n 个整数 输出：从大到小排序的n 个整数（或从小到大排序） 1-2 split 快速排序（枢点法） 问题描述：给定n 个整数，利用枢点法快速排序的思想将其调整成单调序列。 输入：整数的个数n ，以及n 个整数 输出：从大到小排序的n 个整数（或从小到大排序） 1-3 平面最近点对 问题描述：平面内有若干点，设计一算法在O （nlogn ）时间内求出直线距离最近的一对点，并输它们的距离。 输入：点对的数目n 以及n 对点的坐标 输出：最近的点对坐标（x,y ）以及距离d 1-4 棋盘覆盖问题 问题描述：在一个2k ×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该 方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L 型骨牌不得重叠覆盖。 输入：棋盘的行列数n ，棋盘中特殊方格的行列号（x,y ） 输出：棋盘的覆盖方案 1-5 求k 大（小）元素（基于split 枢点法划分） 问题描述：有一数列，设计一分治递归算法，以Ω(nlogn)时间找出其第k 大（小）元素。 输入：整数的个数n 、n 个整数以及k 值 输出：第k 大（小）元素值以及其对应的下标i 1-6 二分检索 问题描述：有一单调序列，设计一分治算法检索出元素x 。 输入：整数的个数n、n个单调增（减）个整数以及需检索的元素值x 输出：最近的点对坐标（x,y）以及距离d 1-7 大整数乘法（10进制） 问题描述：有两个10制的大整数（不少于30位），设计一分治算法，以O（nlogn）时间算出其乘积。 输入：第一个大整数的位数m、第二个大整数的位数n，以及两个大整数x,y 输出：两个大整数的乘积s 1-8 循环赛比赛安排 问题描述：设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次； (2)每个选手一天只能赛一次； (3)循环赛一共进行n-1天。 输入：选手的个数n、n个选手的编号 输出：每天的赛事安排(共n-1天） 1-9 整数的划分问题 问题描述：将正整数n表示成一系列正整数之和：n=n1+n2+…+n k，其中n1≥n2≥…≥n k≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数以及划分情况。 输入：正整数n 输出：n的划分个数以及划分情况 1-10 主元素问题 问题描述：有一个整数数列，数列中元素出现次数超过一半的元素定义为主元素，设计一分治算法，求出主元素。 输入：整数的个数n以及n个整数 输出：如果有主元素，输出主元素以及它们所在的位置；如果没有主元素，输出-1 1-11 全排列的生成 问题描述：给出一个序列，生成这个序列的全排列 输入：整数的个数n以及n个整数 输出：生成这n个数的全排列 贪婪算法 2-1 加油站问题 问题描述：一辆汽车加满油后,可行使n千米。旅途中有若干个加油站。若要使沿途加油次数最少,设计一个有效算法，对于给定的n和k个加油站位置，指出应在哪些加油站停靠加油才能使加油次数最少。 输入：汽车加满油后可行驶千米数n，加油站个数k。以及两两加油站之间的距离。 输出：最少的加油次数m，如果无法到达目的地，则输出“No Solution”。 1.5全排列的生成算法 全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 这里介绍全排列算法四种： (A)字典序法 (B)递增进位制数法 (C)递减进位制数法 (D)邻位对换法 1.5.1字典序法 对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。 [例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列 是:123,132,213,231,312,321。 [注意] 一个全排列可看做一个字符串，字符串可有前缀、后缀。 1）生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。 / 1.5.2递增进位制数法 1)由排列求中介数 在字典序法中，中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。 在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2—n)一致。可看出n-1位的进位链。右端位逢2进1，右起第2位逢3进1，…，右起第i位逢i+1进1，i=1,2,…,n-1. 这样的中介数我们称为递增进位制数。上面是由中介数求排列。 由序号（十进制数）求中介数（递增进位制数）如下： m=m1,0≤m≤n!-1 m1=2m2+kn-1,0≤kn-1≤1 m2=3m3+kn-2,0≤kn-2≤2 …………… mn-2=(n-1)mn-1+k2,0≤k2≤n-2 mn-1=k1,0≤k1≤n-1 p1p2…pn←→(k1k2…kn-1)↑←→m 在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。为方便起见，令ai+1=kn-1，i=1,2,…,n-1 (k1k2…kn-1)↑=(anan-1…a2)↑ ai：i的右边比i小的数字的个数 在这样的定义下， 有839647521←→(67342221)↑ 枚举法中的字典排列 我明天先吃什么呢？先吃汉堡，不不，还 是 先吃玉米，哎，还是先吃饼干 吧！到底 先吃什么呢？共有多少种不同的吃 法？ 基础例题: 在上一讲中我们学习了简单的枚举法一一直接把所有情况一一列举出来. 接枚举很有可能产生重复或者遗漏， 这时就需要有一些特别的方法来帮助我们枚举出所有情况. 本讲就 但如果问题较为复杂，直 如果我把这三个东西都带回去, 天吃1个，还可以再吃3天呢？ 主要介绍两种枚举的方法：字典排列法和树形图法. 首字母相同的单词都在一起 同学们可以翻一下英汉字典，不难发现字典中单词排列的规律：整本字典按首字母从 a 到z 排列, 在首字母相同的单词中, 再按照第2个字母从a 到z 的顺序排列, 然后是 个字母，第4个字母所谓“字典排列法”，就是指在枚举时，像字典里的单词顺序那样排列出 3各一次可以组成多少个不同的三位数？用字典排列法枚举时，每个位置都勒* 按从小到大排列，枚举的顺序是：123, 132, 213, 231 , 312, 321 .下面我们用字典排列法来解决几个 问题. 例题1 .卡莉娅、墨莫、小高三个人去游乐园玩，三人在藏宝屋中一共发现了5件宝物，三人找到 的宝物数量共有多少种不同的可能？（可能有人没有发现宝物） 分析：每个人最少找到几件宝物？最多呢？ 练习： 1.老师准备了6个笔记本奖励萱萱、小高和墨莫三人，每人至少得到1本笔记本，请问：老师有 多少种不同的奖励方法？ 例题2 ?老师要求每个同学写出3个自然数，并且要求这3个数的和是8 ?如果两个同学写出的3 个自然数相同，只是顺序不一样，则算是同一种写法?试问：同学们最多能得出多少种不同的写法？ 分析：注意顺序不同算一种写法，也就是三个数分别为（1、2、5）、（2、5、1 ）和（5、1、2）都 算同一种写法. 练习： 2.三个大于0的整数之和（数与数可以相同）等于10，共有多少组这样的三个数? 用字典排序法枚举的时候，判断题目要求到底是“交换顺序后算作两种”还是“交换顺序后仍然是同一种”非常关键?往往题目中要求“交换顺序后仍然是同一种”，那么枚举的每个结果里就没有明确 的顺序关系；反之，那么枚举时要注意每个结果中应该都符合一定的顺序关系. 在求解计数问题时，审题非常关键?往往一字之差就会有天壤之别. 枚举法是解决计数问题的基础，但是对于比较复杂的问题，如果直接枚举很容易出现重复或者遗 漏.这时就需要预先把所有情形分成若干小类，针对每一小类进行枚举. 例题3 如下图所示，有7个按键，上面分别写着：1、2、3、4、5、6、7这七个数字?请 问： （1）从中选出2个按键，使它们上面的数字的差等于2, 一共有多少种选法？ ftp f 1ft 0 排列组合——排列公式的推理和组合 加法原理和乘法原理，是排列组合中的二条基本原理，在解决计数问题中经常运用。掌握这两条原理，并能正确区分他们，至关重要。 加法原理 若完成一件事情有3类方式，其中第一类方式有1种方法，第二类方式有3种方法，第三类有2种方法，这些方法都不相同，但任选一种方法都可以完成此事，则完成这件事情共有1+3+2=6种方法，这一原理称为加法原理。例如:从甲地到乙地有三类方式，一是汽车，二是火车，三是飞机。若一天中汽车有2班，火车有4班，飞机有一班，那么从甲地到乙地共有多少种不同的走法。共有2+4+1=7种。 乘法原理 若完成一件事情分r个步骤，其中第一个步骤有m1种方法，第二个步骤有m2种方法……第步骤共有mr种方法，各步骤连续或同时完成，这件事才算完成，则完成这件事共有m1*m2*……*mr种方法。例如:从甲地到丙地必须经过乙地。从甲地到乙地有4条路线，从乙地到丙地有3条路线，问从甲地到丙地共有多少种不同的走法？解：要从甲地到达丙地，必须经过两个步骤：先从甲地到乙地，有4条路线；再从乙地到丙地，有3条路线。只有这两个步骤都完成了，才能完成这种事情，缺少哪一个步骤都不行。因此从甲地到丙地共有4*3=12种走法。 加法原理和乘法原理的区别 以上两个基本原理在排列组合问题中将会反复使用。这两个原理回答的都是关于完成一件事情的不同方法的种数问题，但是又有根本区别。加法原理针对的是“分类”问题，若完成一件事情有多类方式，每一类方式的各种方法相互独立，用其中任何一种方法都可以完成这件事情，则用加法原理；而乘法原理针对的是“分步”问题，若完成一件事情必须依次经过多个步骤，每一个步骤的各种方法相互依存，只有各种步骤都完成才算做完成这种事情，则这时用乘法原理。 排列数公式推理过程 例：用1、2、3这3个数字可以组成多少个数字十位和个位不重复的两位数？解：要组成数字不重复的两位数，需要经过两个步骤：第一步确定十位上的数，数字1、2、3都可以放在十位上，共有3种方法；第二步确定个位上的数，因为要求个位数与十位数不能重复，所以个位上的数，只能从三个数字中去掉十位数后所剩的两个数字中任选一个，共有2种方法。只有十位和个位上的数都确定了，才能组成数字不重复的两位数，这两个步骤缺少哪一个都不行。因此，根据乘法原理，3*2=6. 上例中，我们把数字1、2、3称为元素。组成数字不重复的两位数这个问题，从3个不同的元素中任取2个，然后按顺序排成一列数，由于这样的排列与数字不重复的两位数是一一对应的，因此求数字不重复的两位数的个数等同于求这样的排列个数。 推理过程：从n个不同元素中取出m个不同元素排成一列，必须经过m 个步骤。第一步，确定第1个位置上的元素,可以从这n个元素中任取1个放在这个位置上，共有n种方法，即n-(1-1)括号内为位置数减1；第 全排列的生成算法对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。字典序法按照字典序求下一个排列的算法 /*例字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。注意一个全排列可看做一个字符串，字符串可有前缀、后缀。*/生成给定全排列的下一个排列所谓一个全排列的下一个排列就是这一个排列与下一个排列之间没有其他的排列。这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。/*例 839647521是1—9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。算法: 由P1P2…Pn 生成的下一个排列的算法如下:1. 求i=max{j| Pj-1 算法分析与设计实验报告 第 2 次实验 这次的实验和上一次的字典序问题有一些相似，主要不同的地方在于要写出下 附录：完整代码 #include for(int i=end;i>=begin;i--) p[i]=temp[end-i]; } int cal_a(int a,int b)//计算阶乘 { int answer=1; if(a==0&&b==0) return 1; for(int i=0;i 1、数列全排列递归算法； 2、在不打印所有全排列时，数列长度分别为10、11、12、13时全排列花费时间测试，修改N的值重新编译即可运行测试； 3、如果需要打印全排列，打开perm函数中的注释掉的两行printf语句即可。 #include { int i = 0; if (begin == end){ for ( i = 0; i < N ; i++){ //printf("%d", list[i]); } //printf("\n"); } else{ for (i = begin; i <= end; i++) { swap(begin,i); perm(list,begin+1,end); swap(begin,i); } } } int main(int argc, char *argv[]) { int *list=a; int i; perm(list, 0, N-1); for (i = 0; i < N; i++){ printf("%d", list[i]); } return 0; } 。 算法导论复习——常见算法思想 PPT2-1： 1.堆排序（选择类排序，不稳定） （1）初始化操作：将R[1..n]构造为初始堆； （2）每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。 时间复杂度是：O（nlgn） 2.归并排序 ) 归并排序采用分治法思想的稳定的排序。算法思想是先使每个子序列有序，再使子序列段间有序。 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。 时间复杂度是：O（nlgn） 3.快速排序（交换类排序，不稳定） | （1）通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据 都比另外一部分的所有数据都要小； （2）然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 时间复杂度是：O（nlgn）。 4.分治法实现大数相乘 将a，b写成前一半数字和后一半数字相加的形式，例如若 a = 5423678，那么a1 = 542，a0 = 3678（注意若不是偶数截取较小一半） 这样a和b相乘就可以写为：a * b = { a1 * 10^(n1/2) + a0 } * { b1 * 10^(n 2/2) + b0 } （ 展开后整理得： a * b = a1*b1 * 10^[ (n1+n2)/2 ] + a1*b0 * 10^(n1/2 ) + a0*b1 * 10^(n2/2) + a0*b0 四项 这样就很容易递归的来求a * b，如果你嫌分解后的数还太大，就可以继续分解。（你可以自己规定在何时结束递归） 时间复杂度是：O（nlgn） 对于使用递归解决排列和组合的问题，俺看了很多篇参考资料，可惜的是有点难以理解别人的写法，跟MSDN一样，字都是中文，可是合起来就不知道是啥意思了，同样都是代码，每一句都能看明白，可就是不知道，他在这里为啥要写这一句，这一句在整个程序中的地位，还是脑子不好使，中学的时候数学没学好，这么些年又没好好的锻炼脑子，生锈了。 对于全排列来说，咱们还是从最简单的开始吧。 序列中只有一个元素：那么全排列就只有一种，{1}就是这个序列本身。 序列中有两个元素：那么全排列有两种方式，{1，2}，{2，1}。 序列中有三个元素：那么全排列有六种方式，{1，2，3}，{1，3，2}，{2，1，3}，{2，3，1}，{3，1，2}，{3，2，1}。 如果将排列的结果做成一个整数的话，那么对于三个元素的全排列结果应该是：{123}，{132}，{213}，{231}，{312}，{321}，这六个数有没有什么特点？ 当然有。 1.它们都是由1，2，3这几个字符组成的。 2.3>2>1。 3.123<132<213<231<312<321。 这个垃圾结论能替我们解决问题吗？ 当然能。 还记得我们怎么理解二进制的吗？ 还记得我们怎么理解八进制的吗？ 还记得我们怎么理解十六进制的吗？ 二进制中包含两个字符：0，1。 八进制中包含八个字符：0，1，2，3，4，5，6，7。 十六进制中包含十六个字符：0，1，2，3，4，5，6，7，8，9，A，B，C，D，E，F。 俺的乖乖，数字么呢？字母都来咧，那些个A呀，B呀，C呀，只是一些符号而已，它们在十六进制中代表的是10，11，12，13，14，15而已。 为嘛非得用ABCDEF呢？能不能用其他的字符呢？ 当然可以。甚至于我们把ABCDEF可以改成“啊吧才的饿飞”，只有它依然代表的是10，11，12，13，14，15就行了。 为嘛会用的上ABCDEF呢？ 呵呵，简单了，因为咱们平常用的数字中没有一个单独的符号用来表达10，11，12，13，14，15而已，咱们为这些值找了个代表而已。 好了，扯的够远了，往回扯。 回到八进制中，为嘛八进制中没有ABCDEF呢？ 简单的回答是：咱们平常用的数字可以完全拿来表达八进制中的每个单独的数字，就是说，够用了，用不着折腾了 复杂的回答是：可以有ABCDEF这些字母，反正这些字母仅仅是个代表而已。 改成{1，2，3，4，5，6，7，8}行不？当然行。不就是个符号么。 二进制的改成{1，2}行不，也行；改成{2，3}行不，也行。 无论是{1，2}还是{2，3}仅仅是个符号，咱们要做的工作是保证符号中的大小关系，比如1<2，2<3就行了。 那么再次变态一点：{1，4}行不？当然行，对于二进制来说，只要1<4就行了。那么{3，8}也行喽？当然。 好了，我们已经够变态的了，不妨再变态一点。 既然都已经有了二进制，八进制，十六进制，为嘛不能整个三进制呢？ 精品文档 全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1?n的n个数字的排列一一对应，因此 在此就以n 个数字的排列为例说明排列的生成法。 n 个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从它的 前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。 全排列的生成法通常有以下几种：字典序法递增进位数制法递减进位数制法邻位交换法 递归类算法 1. 字典序法 字典序法中，对于数字1、2、3 ......n 的排列，不同排列的先后关系是从左到右逐 个比较对应的数字的先后来决定的。例如对于5个数字的排列 1 2354和12345，排列12345 在前，排列12354 在后。按照这样的规定， 5 个数字的所有的排列中最前面的是 1 2345 ，最后面的是54321 。 字典序算法如下： 设P是1?n的一个全排列： p=p1p2 .... pn=p1p2 ...... pj-1pjpj+1 ..... p k-1pkpk+1 .... pn 1 ）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j 从左端开始计算），即j=max{i|pi排 列 组 合 公 式 及 排 列 组 合 算 法
算法分析与设计总结
排 列 组 合 公 式 及 排 列 组 合 算 法 ( 2 0 2 0 )
查字典技巧口诀及三种方法
全排列生成算法
2枚举法中的字典排列
补充全排列算法C语言实现
算法设计与分析
全排列问题的解析
高斯小学奥数含答案三年级(上)第02讲枚举法中的字典排列
排 列 组 合 公 式 及 排 列 组 合 算 法
全排列生成算法
排列的字典序问题
c语言递归算法实现数列全排列
算法分析与设计常见算法思想
字典排序法
全排列的生成算法