程式扎記: [ Math CC ] Probability and Statistics - C(N, K)

標籤

2012年9月10日 星期一

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

Preface : 
由於我的記憶實在不好, 所以整理一下常用數學概念筆記方便日後參考. 這裡要說明的是 C(N,K) 問題. 

C(N,K) - N 取 K 問題 : 
考慮有問題如下 : 
 

這邊的 C(N,K) 指的是從一個集合大小為 N 中取出 K 的 items 不考慮順序的可能組合. 考慮 N=3, K=2 的話可以如下圖理解 : 
 

公式推導 : 
由問題的提示我們可以知道 C(N,K) = C(N-1,K) + C(N-1,K-1). 但這個公式是怎麼來的呢? 從集合中的某個物件的角度來說, 你可以這麼看 : 
C(N,K) = (某個物件被選取的組合) + (某個物件沒被選取的組合)

那麼我們來看 (某個物件被選取的組合) 這個含意就是說 : 某一個物件被選取下, 剩下 K-1物件從 N-1物件中挑選的組合 -> C(N-1, K-1) 
那麼 (某個物件沒被選取的組合) 也就是說 : 從 N-1 個物件 (去掉該被選取的物件), 取出 K 個物件 -> C(N-1, K) 
所以最後我們得到 : C(N,K) = C(N-1,K) + C(N-1,K-1) 

事實上這是一個很有名的定理 - 巴斯卡法則 : 

在上面 "巴斯卡法則" 鏈結到 wiki 上面有對應的推導過程, 公式推導是死的. 重點要了解背後的物理意義. 我們知道公式如下 : 
 

其中 n! 你可以理解在有 n 個物件的袋子依序取出 n 個物件的可能排列組合(考慮順序). 如 n=3 的話 : 
 
(也就是說 n=3, n!=3*2*1

那 m! 指的是我們取出來的 m 個物件中, 這 m 個物件的取出順序是不被考慮的; 而 (n-m)! 則是為了移除在 n! 中那些沒被選到的物件排列組合 : 



範例代碼 :
下面使用代碼利用 Recursion 將公式 C(N,K) = C(N-1,K) + C(N-1,K-1) 實作出來, 可以發現函數 CSize() 得到的結果恰為上面公式 :

  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. }  
接著下面函數 C(int N, int K) 會幫我們從 Collection {1,2,...N} 取出 K 個 Items 中所有可能的 Combination (不考慮順序) :
  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();  
  24.     for(Integer i:set) if(i!=except) newSet.add(i);  
  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
  46.         comb.add(charSet);  
  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);  
  12.         combInStr.add(sb.toString());  
  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!