算法之排列与组合算法
本文介紹了常用的排列組合算法，包括全排列算法，全組合算法，m個數選n個組合算法等。
2. 排列算法
常見的排列算法有：
(A)字典序法
(B)遞增進位制數法
(C)遞減進位制數法
(D)鄰位對換法
(E)遞歸法
介紹常用的兩種：
(1) 字典序法
對給定的字符集中的字符規定了一個先后關系，在此基礎上按照順序依次產生每個排列。
[例]字符集{1,2,3},較小的數字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321。
生成給定全排列的下一個排列 所謂一個的下一個就是這一個與下一個之間沒有字典順序中相鄰的字符串。這就要求這一個與下一個有盡可能長的共同前綴，也即變化限制在盡可能短的后綴上。
算法思想：
設P是[1,n]的一個全排列。
P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn , j=max{i|Pi<Pi+1}, k=max{i|Pi>Pj} ,對換Pj，Pk，將Pj+1…Pk-1PjPk+1…Pn翻轉， P’= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一個
例子:839647521的下一個排列.
從最右開始,找到第一個比右邊小的數字4(因為4<7，而7>5>2>1),再從最右開始,找到4右邊比4大的數字5(因為4>2>1而4<5),交換4、5,此時5右邊為7421,倒置為1247,即得下一個排列:839651247.用此方法寫出全排列的非遞歸算法如下
該方法支持數據重復，且在C++ STL中被采用。
(2) 遞歸法
設一組數p = {r1, r2, r3, … ,rn}, 全排列為perm(p)，pn = p – {rn}。則perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), … , rnperm(pn)。當n = 1時perm(p} = r1。
如：求{1, 2, 3, 4, 5}的全排列
1、首先看最后兩個數4, 5。 它們的全排列為4 5和5 4, 即以4開頭的5的全排列和以5開頭的4的全排列。
由于一個數的全排列就是其本身，從而得到以上結果。
2、再看后三個數3, 4, 5。它們的全排列為3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六組數。
即以3開頭的和4,5的全排列的組合、以4開頭的和3,5的全排列的組合和以5開頭的和3,4的全排列的組合.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <stdio.h> int n = 0; void swap(int *a, int *b) { ??int m; ??m = *a; ??*a = *b; ??*b = m; } void perm(int list[], int k, int m) { ??int i; ??if(k > m) ??{ ????for(i = 0; i <= m; i++) ??????printf("%d ", list[i]); ????printf("\n"); ????n++; ??} ??else ??{ ????for(i = k; i <= m; i++) ????{ ??????swap(&list[k], &list[i]); ??????perm(list, k + 1, m); ??????swap(&list[k], &list[i]); ????} ??} } int main() { ??int list[] = {1, 2, 3, 4, 5}; ??perm(list, 0, 4); ??printf("total:%d\n", n); ??return 0; } |
3. 組合算法
3.1 全組合
在此介紹二進制轉化法，即，將每個組合與一個二進制數對應起來，枚舉二進制的同時，枚舉每個組合。如字符串：abcde
00000 <– –> null
00001<– –> e
00010 <– –> d
… …
11111 <– –> abcde
3.2 從n中選m個數
(1) 遞歸
a. 首先從n個數中選取編號最大的數，然后在剩下的n-1個數里面選取m-1個數，直到從n-(m-1)個數中選取1個數為止。
b. 從n個數中選取編號次小的一個數，繼續執行1步，直到當前可選編號最大的數為m。
下面是遞歸方法的實現：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | /// 求從數組a[1..n]中任選m個元素的所有組合。 /// a[1..n]表示候選集，n為候選集大小，n>=m>0。 /// b[1..M]用來存儲當前組合中的元素(這里存儲的是元素下標)， /// 常量M表示滿足條件的一個組合中元素的個數，M=m，這兩個參數僅用來輸出結果。 void combine( int a[], int n, int m,? int b[], const int M ) { ??for(int i=n; i>=m; i--)?? // 注意這里的循環范圍 ??{ ????b[m-1] = i - 1; ????if (m > 1) ??????combine(a,i-1,m-1,b,M); ????else???????????????????? // m == 1, 輸出一個組合 ????{ ??????for(int j=M-1; j>=0; j--) ??????cout << a[b[j]] << " "; ??????cout << endl; ????} ??} } |
(2) 01轉換法
本程序的思路是開一個數組，其下標表示1到n個數，數組元素的值為1表示其代表的數被選中，為0則沒選中。
首先初始化，將數組前n個元素置1，表示第一個組合為前n個數。
然后從左到右掃描數組元素值的“10”組合，找到第一個“10”組合后將其變為“01”組合，同時將其左邊的所有“1”全部移動到數組的最左端。
當第一個“1”移動到數組的n-m的位置，即n個“1”全部移動到最右端時，就得到了最后一個組合。
例如求5中選3的組合：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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 |
4. 參考資料
(1) http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html
(2) http://comic.sjtu.edu.cn/thucs/GD_jsj_025y/text/chapter01/sec05/default.htm
(3) http://blog.csdn.net/sharpdew/archive/2006/05/25/755074.aspx
(4) http://xiaomage.blog.51cto.com/293990/74094
總結
以上是生活随笔為你收集整理的算法之排列与组合算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 八数码 poj 1077 广搜 A* I
- 下一篇： 排列组合算法的实现代码