## 2012年9月10日 星期一

### [ Math CC ] Probability and Statistics - C(N, K)

Preface :

C(N,K) - N 取 K 問題 :

C(N,K) = (某個物件被選取的組合) + (某個物件沒被選取的組合)

(也就是說 n=3, n!=3*2*1

1. /**
2. * BD : C(N,K) = C(N-1,K) + C(N-1,K-1)
3. *      1. You can treat C(N-1,K-1) -> Specific one is chosen from collection . So K-1 left. from N-1 collection
4. *      2. You can treat C(N-1,K) -> The item 1 has specific one being chosen.
5. *         This item is the combination which not including that specific one.
6. * @param col : The collection with size .
7. * @param K : The number to pickup from collection .
8. * @return The size of array of combination of pickup items from collection size= C(N,K).
9. */
10. public static int CSize(int N, int K)
11. {
12.     if(Nreturn -1// The collection size should not smaller than .
13.     else if(N==K) return 1// If the collection size equals means only one possibility.
14.     else if(K==0 || N==0return 1// If either collection size=0 or K=0, return 1 as defined by question.
15.     else // If the collection size larger than , fit in the equation : C(N,K)=C(N-1,K) + C(N-1,K-1)
16.     {
17.         return CSize(N-1,K)+CSize(N-1,K-1);
18.     }
19. }

1. /**
2. * BD : Return all possible combination of C(N,K).
3. *      The collection is {1,2,...,N}.
4. * @param N : The size of collection.
5. * @param K : K items will be pickup.
6. * @return The all possible combination of K items from collection.
7. */
8. public static Set> C(int N, int K)
9. {
10.     Set col = new HashSet();
11.     for(int i=1; i<=N; i++) col.add(i);
12.     return C(col, K);
13. }
14.
15. public static Set> C(Set col, int K){
16.     Set> comb = new HashSet>();
17.     // Remove duplicate items with different order. 321=123=231 etc.
18.     return _C(col, "", comb, K);
19. }
20.
21. protected static Set _genSet(Set set, int except)
22. {
23.     Set newSet = new HashSet();
25.     return newSet;
26. }
27.
28. public static Set> _C(Set curCol, String inSelect, Set> comb, int K)
29. {
30.     if(curCol.size()>K)
31.     {
32.         for(Integer i:curCol)
33.         {
34.             if(inSelect==null) inSelect = "";
35.             Set subSet = _genSet(curCol, i);
36.             _C(subSet, inSelect, comb, K);
37.             _C(subSet, inSelect+i, comb, K-1);
38.         }
39.         return comb;
40.     }
41.     else if(curCol.size()==K)
42.     {
43.         for(int i:curCol) inSelect=inSelect+i;
44.         Set charSet = new TreeSet();
45.         for(int i=0;i
47.         return comb;
48.     }
49.     else
50.     {
51.         return comb;
52.     }
53. }

1. public static void main(String args[])
2. {
3.     int N = 5, K=3;
4.     System.out.printf("\t[Info] N=%d; K=%d; C(N,K)=%d.\n", N, K, Combinatoric.CSize(N,K));
5.     Set> colList = Combinatoric.C(N, K);
6.
7.     // Sorting the result
8.     Set combInStr = new TreeSet();
9.     for(Set chars:colList) {
10.         StringBuilder sb = new StringBuilder("");
11.         for(Character c:chars) sb.append(c);
13.     }
14.
15.     // Printout the combinations
16.     for(String s:combInStr)
17.     {
18.         System.out.printf("\t%s\n", s);
19.     }
20. }

[Info] N=5; K=3; C(N,K)=10.
123
124
125
134
135
145
234
235
245
345

## 關於我自己

Where there is a will, there is a way!