排列组合算法

《排列组合算法》由会员分享，可在线阅读，更多相关《排列组合算法（11页珍藏版）》请在金锄头文库上搜索。

1、排列组合算法全排序算法一排列生成算法排列生成有几种典型算法，这些算法 都很有成效.它们在实际中具有广泛 应用价值.L序数法2, 字典序法3, 邻位互换法(Johnson-Trotter)4, 轮转法全排列在很多程序都有应用，是一个很常见的算法，常规的算法是一种递归的算法，这种算 法的得到基于以下的分析思路。 给定一个具有n个元素的集合(n=1)，要求输出这个集 合中元素的所有可能的排列。设R=r1,r2,.,rn是要进行排列的n个元素，Ri=R-ri.Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列。(1) 当n=1时，Perm(R) = (r),其中r是集合R中唯

2、一的元素；(2) 当 n1 时，Perm(R)可由(r1)+Perm(R1),(r2)+Perm(R2),.,(rn)+Perm(Rn)构成。 此算法就是按照上述思想来设计的。不难想出，次算法使用递归思想比较容易实现。设Perm(list,k,m)递归地产生所有前缀是list0:k-1,且后缀是listk:m的全排列的所 有排列。那么调用算法Perm(list,0,n-1)则产生list0:n-1的全排列。A:以abc为例，我们首先将a固定在第一位，然后排列bc，当bc排列完成后，我们会将b 固定在第一位，也就是交换a和b的位置，变成bac，然后排列ac，当ac排列完成后，我 们需要将c固定在

3、第一位，先将a和b的位置复原，在交换a和c的位置即可。因此，用递 归来求解再自然不过。对于字符串abcdedfgh.，在以begin为开头的子串中，我们要依次将子串的每一个字符固定在首位，这需要依次swap操作，然后我们递归的处理子串开头 之后的更小子串的排列，当处理好之后，我们回到该子串，再将刚才的swap操作重新操作 一遍。一 4 34 Tirr-1-1 rr 刀-3一3 -3 7 L4 4 -2L 2 一2 J 2r一 33T3t1一 1 一 1 -4 14 T 4 f 3F 33一 3 J222一 2 W -2 5二 2一 I T 4-4-3. 31 3L321 2 4-2 21 21

4、 231 3H 147 1r IL1J 11j -4*22 L2J 2 2 l2一 J 4P3 -111L1L 44T 1 -3J 33 L 34 veld swap (crie.r * crar *k)5 6 chsrtemp;temp = m a; i =*t;9=temp:10 :字典序排列字典序排列就是按照字典a-z,1-9的顺序给出字符串的顺序全排列，例如abc的全排列就是 从abc 一直排到cba。那么给定一个字符串，怎么找出恰好大于该字符串的下一个排列呢？ 我们考虑如下的步骤：1、假设字符串为p1p2.pn,我们从后往前寻找第一个符合pjpj+1条件的字符pj，也就是 说，p1p

5、2pjTpjpj+1pn 中 pjpj+2pn。2、再次从后往前寻找第一个大于pj的字符pk，也就是说，p1p2pjTpjpj+1pk-1pkpk+1pn 中从后往前pkpj并且pk+1,pnpk-1pjpk+1pn。4、为了得到恰好大于该字符串的下一个排列，我们看到从j+1之后的字符串是降序排列的， 我们将其翻转，就可以得到想要的结果了。那么什么时候整个过程结束呢？当再也找不到符合条件的j时，说明当前的字符串已经是逆 序的了，也就是字典序最大。例字符集1,2,3,较小的数字较先，这样按字典序生成的全排列 是：123,132,213,231,312,321。例2.3设有排列(p) =27635

6、41,按照字典式 排序,它的下-个排列是谁？(q) =2764135.(1) 2763541 找最后一个正序35(2) 2763541 找3后囱比3大的最后一个数(3) 2764531 交换3,4的位置(4) 2764135把4后面的531反序排列为135即得到最后的排列(q)32 vcid perm* src)33 34 if src = HULL)二二 F36int len - strle. (3ic);3839 while(1)40 (41 sic);4243 int last = ler-1;44 int Bec_last = len-2;45 whilesec last=0 & sr

7、cfsec lastsicsec last+1)46 sec last;47 i_f ( sec lastC48 trealr;49 |50 while(arc lastbxc3ec_last)51 一一last;5253 swap src lastr src sec last);54 _55 int 己r匕；56 for ( = iec last+L,ti= Le: -L; c r59:-6061 I62 :-12 veld pern (caarcf inx start.f it leri)13 (14 int i15 1 (start= =len.)16 f17 for ( =;= e:

8、; i+)18 (rr%cr mrr i);19 (rrnrr);20 ；21 else22for ( = :tart.; =len; :_+)24 1swap (&s rc , = wru :tart);2Gpezsra(_3c, start +_, len)-27svap ( &btc f ： ;rc ：tart);25 :-一29 ；-30 F去掉重复的全排列的递归实现去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。G4 去重夏的全换列65 int己h frsrcf in.t st artferid)66 G7wMLe (Btaz- end)68 69 f (sic

9、 start =5ic enc )70 71 丁wt二丁二 L ;72 273 staii 44,74 ?ret0:76 :-77 veil pami_Tiodj.p (car frsrcr int start, int len)78 79 i;80 start = Is)81 f|for (. =?;:=旦：i_+)83 prirztf C rr%crrr Bre i);84 printf irnrr) r85 86 e_se87 1for ( - :tart; i =ler; : +)89 90 i_f z_3 swap srer startr 5.)91 - 一92 3wap (& wr

10、e： r &src m匕己：rt ); permCarcf strt+_r len);94 swap ( &3tc 广 &src m匚吕:ct );95 :-9G；97 ；-98 口口组合算法题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的 组合有a、b、c、ab、 ac、 bc、 abc。上面我们详细讨论了如何用递归的思路求字符串的排列。同样，本题也可以用递归的思路来 求字符串的组合。假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。 针对第一个字符，我们有两种选择：第一是把这个字符放到组合中去，接下来我们需要在剩 下的n-1

11、个字符中选取m-1个字符；第二是不把这个字符放到组合中去，接下来我们需要在 剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码：void Conbination(char *string)assert(string != NUL_);vectorcchar? result;int i j length = strlen(stririE);for(i = 1 ; 1 = length ; +i) 匚onibination(string , i j result);uoidl 匚ombination(char * string , int number , v

12、ector ire suit)assertCstrine != NHL_)j if(number = 口)static int nun = 1;print-(第湖个组合VtnLm+);vector: : iterator iter = 已suit. begin ();for( ; iter != result. end() ; 4-4-iter) priirtf(Kc *lter);print( ,rn,r);return ;if (*string： =)return ;result. pu5h_bsclc(;Combinatio-n (string + 1 f number - 1 s re

13、sult);result .pup_backC);匚cmbiriBtio-n(string + 1 , number result);字符串全排列扩展一-八皇后问题题目：在8X8的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后不得处 在同一行、同一列或者同一对角斜线上。下图中的每个黑色格子表示一个皇后，这就是一种 符合条件的摆放方法。请求出总共有多少种摆法。这就是有名的八皇后问题。解决这个问题通常需要用递归，而递归对编程能力的要求比较高。 因此有不少面试官青睐这个题目，用来考察应聘者的分析复杂问题的能力以及编程的能力。由于八个皇后的任意两个不能处在同一行，那么这肯定是每一个皇后占据一

14、行。于是我们可 以定义一个数组ColumnIndex8，数组中第i个数字表示位于第i行的皇后的列号。先把 Columnindex的八个数字分别用0-7初始化，接下来我们要做的事情就是对数组Columnindex 做全排列。由于我们是用不同的数字初始化数组中的数字，因此任意两个皇后肯定不同列。 我们只需要判断得到的每一个排列对应的八个皇后是不是在同一对角斜线上，也就是数组的 两 个下标 i 和 j， 是不是 i-j=Columnindexi-Columnj或 者 j-i=ColumnIndexi-Columnindexjo关于排列的详细讨论，详见上面的讲解。接下来就是写代码了。思路想清楚之后，编码并不是很难的事情。下面是一段参考代码:void eicr:()ccnst int-