1.可重復排列：abc三個字符組成的所有長度為3的字符串，aaa,aab,aac......ccc 一共27種
利用遞歸的思想，第一個字符可以從abc中選擇一個，三種選擇，之后問題轉化為abc組成長度為2的字符的情況，循環遞歸后可以求出所有的可能。控制好循環退出條件即可。
利用遞歸可以處理，不知道字符長度的情況下，即通用處理。如果知道長度，只需要利用多層循環，也可以得出結論。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public class permutation { public static void main(string[] args) { char[] chs = {'a','b','c'}; per(new char[3], chs, 3-1); } public static void per(char[] buf, char[] chs, int len){ if(len == -1){ for(int i=buf.length-1; i>=0; --i) system.out.print(buf[i]); system.out.println(); return; } for(int i=0; i<chs.length; i++){ buf[len] = chs[i]; per(buf, chs, len-1); } } } |
可重復選擇，一共27種情況，結果如下圖所示
2.全排列：還是abc三個字符，全排列即字符不能重復。最后 3*2 =6種結果
可以利用1中的方法，只要判斷3個字符是否相等，都不相等的才是需要的全排列里的一個。這樣的時間復雜度為n^n,而全排列的種類為n！所以需要設計一種n！的算法。
也可以利用遞歸，第一個字符串一共有n種選擇，剩下的變成一個n-1規模的遞歸問題。而第一個字符的n種選擇，都是字符串里面的。因此可以使用第一個字符與1-n的位置上進行交換，得到n中情況，然后遞歸處理n-1的規模，只是處理完之后需要在換回來，變成原來字符的樣子。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class arrange { public static void main(string[] args) { char[] chs = {'a','b','c'}; arrange(chs, 0, chs.length); } public static void arrange(char[] chs, int start, int len){ if(start == len-1){ for(int i=0; i<chs.length; ++i) system.out.print(chs[i]); system.out.println(); return; } for(int i=start; i<len; i++){ char temp = chs[start]; chs[start] = chs[i]; chs[i] = temp; arrange(chs, start+1, len); temp = chs[start]; chs[start] = chs[i]; chs[i] = temp; } } } |
運行結果如下圖所示，一共6種組合
3.組合：abc三個字符的所有組合
求所有組合也就是abc各個位是否選取的問題，第一位2中可能，第二位2種。。。所以一共有2^n種。用0表示不取，1表示選取，這樣可以用110這樣的形式表示ab。abc一共的表示形式從0到2^3-1。然后按位與運算，如果結果為1就輸出當前位，結果0不輸出。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class comb { public static void main(string[] args) { char[] chs = {'a','b','c'}; comb(chs); } public static void comb(char[] chs) { int len = chs.length; int nbits = 1 << len; for (int i = 0; i < nbits; ++i) { int t; for (int j = 0; j < len; j++) { t = 1 << j; if ((t & i) != 0) { // 與運算，同為1時才會是1 system.out.print(chs[j]); } } system.out.println(); } } } |
輸出結果如下，第一行為空，表示一個都不取
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://blog.csdn.net/Tredemere/article/details/52815965
