开源.NET排列组合组件KwCombinatorics使用(一)——生成组合序列

浏览数：19 / 时间：2015年06月09日

你还可以参考本博客其他.NET开源项目的相关文章：

【原创】彩票预测算法：离散型马尔可夫链模型          Newlife XCode组件资源目录汇总【2013年版】                   

前言

　　本文今天介绍的.NET开源组件是KwCombinatorics，它是.NET平台一个高效的生成排列组合序列的开源类库，它提供了4种生成排列与组合序列的方式。虽然原理和功能都很简单，但是这个类库在软件测试、组合数学以及密码学等方面都有很大的用处。很早就接触了这个类库，以前在一些小程序中也使用过，有时候为了遍历所有可能的组合，自己去写循环，生成，的确很繁琐，有了KwCombinatorics 之后，都变得简单写了，接下来将详细介绍该类库的使用。
　　KwCombinatorics类库的主页是：http://kwcombinatorics.codeplex.com/
　　本文后面的资源提供了所有源码和帮助文件，以及dll文件的打包下载。可以下载到最新的源代码和帮助文档，目前最新的稳定率版本是4.0,相比之前又增加了几个新功能，并进行了一些优化。
　　该类库简单，只有5个类，dll文件也只有几十kb，下面将介绍几个主要的功能。
 
 
　　排列组合是组合学最基本的概念:
　　排列，是指从给定个数的元素中取出指定个数的元素进行排序的所有情况。
　　组合，是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序的所有情况。

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

　　写篇文章不容易，如果对您有帮助，顺手点个【推荐】吧。

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 算法 class style 代码 com log 使用 html 文件 算法 class style 代码 com log 使用 html 文件

相关文章

随机文章

您可能还喜欢

您可能还喜欢