【原創】開源.NET排列組合組件KwCombinatorics使用(一)——生成組合序列，android開源組件

【原創】開源.NET排列組合組件KwCombinatorics使用(一)——生成組合序列，android開源組件

你還可以參考本博客其他.NET開源項目的相關文章：

【原創】彩票預測算法：離散型馬爾可夫鏈模型          Newlife XCode組件資源目錄匯總【2013年版】                   

【原創】開源.NET下的XML數據庫介紹及入門           【原創】.NET開源壓縮組件介紹與入門    

【開源】.NET開源表達式計算組件介紹與使用           【原創】開源Word讀寫組件DocX介紹與入門

【原創】Matlab.NET混編調用Figure窗體                【原創】Matlab與.NET基於類型安全的接口編程入門  

【原創】C#開源輕量級對象數據庫NDatabase介紹    【原創】數據挖掘之—基於ReliefF和K-means算法的醫學應用實例 

Infer.NET機器學習系列文章目錄

1. Infer.NET連載(一)介紹 ：http://www.cnblogs.com/asxinyu/p/4252769.html 

2. Infer.NET連載(二)貝葉斯分類器例子 ：http://www.cnblogs.com/asxinyu/p/4255921.html  

前言

　　本文今天介紹的.NET開源組件是KwCombinatorics，它是.NET平台一個高效的生成排列組合序列的開源類庫，它提供了4種生成排列與組合序列的方式。雖然原理和功能都很簡單，但是這個類庫在軟件測試、組合數學以及密碼學等方面都有很大的用處。很早就接觸了這個類庫，以前在一些小程序中也使用過，有時候為了遍歷所有可能的組合，自己去寫循環，生成，的確很繁瑣，有了KwCombinatorics 之後，都變得簡單寫了，接下來將詳細介紹該類庫的使用。 　　KwCombinatorics類庫的主頁是：http://kwcombinatorics.codeplex.com/ 　　本文後面的資源提供了所有源碼和幫助文件，以及dll文件的打包下載。可以下載到最新的源代碼和幫助文檔，目前最新的穩定率版本是4.0,相比之前又增加了幾個新功能，並進行了一些優化。 　　該類庫簡單，只有5個類，dll文件也只有幾十kb，下面將介紹幾個主要的功能。   　　本文原文地址：http://www.cnblogs.com/asxinyu/p/4257026.html
  　　排列組合是組合學最基本的概念: 　　排列，是指從給定個數的元素中取出指定個數的元素進行排序的所有情況。 　　組合，是指從給定個數的元素中僅僅取出指定個數的元素，不考慮排序的所有情況。

1.Combination類基本介紹

　　Combination類是根據指定的對象列表，依次升序選擇非重復數字的組合序列，重復是什麼意思呢？就是指定序列中的元素不重復選擇2次。舉個例子：從 0，1，2，3這4個數中，取出3個元素組成序列，那麼共有這麼幾種組合方式：{0,1,2},{0,1,3},{0,2,3},{1,2,3}四種方式，這種情況下，每個組合中，元素只出現一次，否則的話可以重復，那麼就是這樣{0,0,0},{0,0,1}....

Combination類的初始化和使用比較簡單，幾個主要的構造函數如下：

1 Combination()  //Make an empty Combination.  
2 Combination(Int32) //Make a new Combination from the supplied choices of all Picks of Rank 0.  
3 Combination(Combination) //Make a copy of a Combination.  
4 Combination(Int32, Int32) //Make a new Combination from the supplied choices and picks of Rank 0.  
5 Combination(Int32, Int32[]) //Make a new Combination from the supplied elements.  
6 Combination(Int32, Int32, Int64) //Make a new Combination from the supplied choices and picks of the supplied rank.  

參數主要有下面幾個注意點:

choices：要選擇組合序列的個數
picks:可供選擇的數的個數，如果不提供實際的源數據source，默認就是從0開始的整數；
source：可以直接用初始化列表，而不是固定的從0開始
rank：這個屬性是我認為使用這個組件最強大的地方，因為是按照升序生成所有的組合序列， 而rank就是指定你要選擇的在整個組合序列中當前rank位置的組合序列。

下面用幾個例子說明幾個主要方法的使用情況。

2.獲取所有N選K的組合列表

設從{0,1,2,3}4個元素中，每次取2個，所有的組合情況有哪些呢？直接上代碼，比較容易看得懂：

1 var cn = new Combination (choices:4, picks:2);
2 
3 Console.WriteLine ("Choices={0}, Picks={1}:", cn.Choices, cn.Picks);
4 
5 foreach (var row in cn.GetRows())
6     Console.WriteLine ("Rank={0,2}:  {1}", row.Rank, row);

運行結果如下：

1 Choices=4, Picks=2:
2 Rank= 0:  { 0, 1 }
3 Rank= 1:  { 0, 2 }
4 Rank= 2:  { 0, 3 }
5 Rank= 3:  { 1, 2 }
6 Rank= 4:  { 1, 3 }
7 Rank= 5:  { 2, 3 }

 　　那有人問，如果想把選擇1-N的組合個數都取出來，怎麼辦？要循環選擇picks一一生成麼？那樣的話當然可以，但這個組件也直接提供了這個功能，看代碼：

1 var cn = new Combination (choices:4, picks:3);
2 
3 Console.WriteLine ("Choices={0}, Picks={1}:", cn.Choices, cn.Picks);
4 
5 foreach (var row in cn.GetRowsForAllPicks())
6     Console.WriteLine ("Rank={0,2}:  {1}", row.Rank, row);

注意，這段代碼特意改了2個地方：1個是pciks選3，而獲取的方法是GetRowsForAllPicks，不是簡單的GetRows。它的作用就是把所有pick的情況都包括了，看看結果：

 1 Choices=4, Picks=3:
 2 Rank= 0:  { 0 }
 3 Rank= 1:  { 1 }
 4 Rank= 2:  { 2 }
 5 Rank= 3:  { 3 }
 6 Rank= 0:  { 0, 1 }
 7 Rank= 1:  { 0, 2 }
 8 Rank= 2:  { 0, 3 }
 9 Rank= 3:  { 1, 2 }
10 Rank= 4:  { 1, 3 }
11 Rank= 5:  { 2, 3 }
12 Rank= 0:  { 0, 1, 2 }
13 Rank= 1:  { 0, 1, 3 }
14 Rank= 2:  { 0, 2, 3 }
15 Rank= 3:  { 1, 2, 3 }

3.任意對象列表的N選K組合

　　上述例子很清楚的說明了N選K的組合情況。choices為數字，好辦，那如果是其他對象列表，要進行組合選擇，那該如何辦？構造函數也沒有直接用對象列表作為選擇源的啊？其實很簡單，其原理是：先獲取對應 對象列表 長度L，和要選擇對象個數的K 的組合對象Combination (L,K)，然後和第2節中的GetRows一樣，循環，將每一個Combination的選擇作為模版，使用Permute方法將模版應用到對象列表中，選擇出對應位置的對象，進行組合。 　　為了簡單明了，上代碼：

 1 //定義源數據列表
 2 String[] objs = new string[] {"A","B","C","D"};
 3 //初始化同樣長度的組合生成對象
 4 var cn = new Combination (choices:objs.Length, picks:2);
 5 
 6 Console.WriteLine ("Choices={0}, Picks={1}:", cn.Choices, cn.Picks);
 7 
 8 //循環每一個組合
 9 foreach (var row in cn.GetRows ())
10 {
11     Console.Write("Rank={0,2}: ", row.Rank);
12     //將組合映射到對象中，循環獲取組合的每一個對象
13     foreach (var thing in Combination.Permute (row, objs))
14         Console.Write (thing + " ");
15     Console.WriteLine ();
16 }

當然其他對象也類似，大家可以依次類推。

4.高級—獲取任意Rank位置的組合

　　這個功能也是區別於個人手寫的最大亮點，所以一個成熟的功能組件是需要很多付出的，哪怕是一個小功能。關注和使用這個組件的時間超過4年，再次向作者表示感謝。可謂是麻雀雖小五髒俱全。前面已經介紹了，Rank就是相對與所有組合的一個順序號(升序)，而上面介紹的都是通過IEnumerable來一次獲取所有組合，但如果只需要獲取指定位置的組合咋辦，看代碼：

//初始化一個組合，從6個數中，選擇4個的所有組合中，取位置2的組合(從0開始)
var cn = new Combination (choices:6, picks:4, rank:2);
Console.WriteLine ("{0}  n={1}, k={2}, rank={3}\n", cn, cn.Choices, cn.Picks, cn.Rank);

//設置Rank為-1，默認取最後一個位置的組合
cn.Rank = -1;
string text = cn.ToString() + "  n=" + cn.Choices + ", k=" + cn.Picks + ", last=" + cn.Rank;
Console.WriteLine (text);

//將當前Rank+1，的組合
cn.Rank = cn.Rank + 1;
Console.WriteLine ("\n{0}  n={1}, k={2}, rank={3}", cn, cn.Choices, cn.Picks, cn.Rank);

結果如下，對比結果和代碼，應該很容易理解：

1 { 0, 1, 2, 5 }  n=6, k=4, rank=2
2 
3 { 2, 3, 4, 5 }  n=6, k=4, last=14
4 
5 { 0, 1, 2, 3 }  n=6, k=4, rank=0

同樣，還可以通過Picks屬性來獲取每一個組合中所有的元素，如：

1 for (int i = 0; i < cn.Picks; ++i)
2      Console.WriteLine ("Element at {0} is {1}", i, cn[i]);

5.Multicombination類

　　與Combination功能一樣，結構也一樣。只不過選擇是可以重復，Combination是不重復的。 代碼都差不多，就不貼了，有興趣的朋友自己去試試看。

6.資源

　　接下來的幾篇文章將繼續介紹該組件的其他功能。

　　官方網站：http://kwcombinatorics.codeplex.com/

　　源碼和其他資源打包下載：http://pan.baidu.com/s/1c06JVJ6  密碼：mzcx

　　如果本文章資源下載不了，或者文章顯示有問題，請參考 本文原文地址：http://www.cnblogs.com/asxinyu/p/4257026.html

　　寫篇文章不容易，如果對您有幫助，順手點個【推薦】吧。