【原创】开源.NET排列组合组件KwCombinatorics使用(一)—组合生成

       本博客所有文章分类的总目录:本博客博文总目录-实时更新

本博客其他.NET开源项目文章目录:【目录】本博客其他.NET开源项目文章目录

前言

  本文今天介绍的.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类的初始化和使用比较简单,几个主要的构造函数如下: 

 Combination()  //Make an empty Combination.
Combination(Int32) //Make a new Combination from the supplied choices of all Picks of Rank 0.
Combination(Combination) //Make a copy of a Combination.
Combination(Int32, Int32) //Make a new Combination from the supplied choices and picks of Rank 0.
Combination(Int32, Int32[]) //Make a new Combination from the supplied elements.
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个,所有的组合情况有哪些呢?直接上代码,比较容易看得懂:

 var cn = new Combination (choices:, picks:);

 Console.WriteLine ("Choices={0}, Picks={1}:", cn.Choices, cn.Picks);

 foreach (var row in cn.GetRows())
Console.WriteLine ("Rank={0,2}: {1}", row.Rank, row);

运行结果如下:

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

  那有人问,如果想把选择1-N的组合个数都取出来,怎么办?要循环选择picks一一生成么?那样的话当然可以,但这个组件也直接提供了这个功能,看代码:

 var cn = new Combination (choices:, picks:);

 Console.WriteLine ("Choices={0}, Picks={1}:", cn.Choices, cn.Picks);

 foreach (var row in cn.GetRowsForAllPicks())
Console.WriteLine ("Rank={0,2}: {1}", row.Rank, row);

注意,这段代码特意改了2个地方:1个是pciks选3,而获取的方法是GetRowsForAllPicks,不是简单的GetRows。它的作用就是把所有pick的情况都包括了,看看结果:

 Choices=, Picks=:
Rank= : { }
Rank= : { }
Rank= : { }
Rank= : { }
Rank= : { , }
Rank= : { , }
Rank= : { , }
Rank= : { , }
Rank= : { , }
Rank= : { , }
Rank= : { , , }
Rank= : { , , }
Rank= : { , , }
Rank= : { , , }

3.任意对象列表的N选K组合

  上述例子很清楚的说明了N选K的组合情况。choices为数字,好办,那如果是其他对象列表,要进行组合选择,那该如何办?构造函数也没有直接用对象列表作为选择源的啊?其实很简单,其原理是:先获取对应 对象列表 长度L,和要选择对象个数的K 的组合对象Combination (L,K),然后和第2节中的GetRows一样,循环,将每一个Combination的选择作为模版,使用Permute方法将模版应用到对象列表中,选择出对应位置的对象,进行组合。
  为了简单明了,上代码:
 //定义源数据列表
String[] objs = new string[] {"A","B","C","D"};
//初始化同样长度的组合生成对象
var cn = new Combination (choices:objs.Length, picks:); Console.WriteLine ("Choices={0}, Picks={1}:", cn.Choices, cn.Picks); //循环每一个组合
foreach (var row in cn.GetRows ())
{
Console.Write("Rank={0,2}: ", row.Rank);
//将组合映射到对象中,循环获取组合的每一个对象
foreach (var thing in Combination.Permute (row, objs))
Console.Write (thing + " ");
Console.WriteLine ();
}

当然其他对象也类似,大家可以依次类推。

4.高级—获取任意Rank位置的组合

  这个功能也是区别于个人手写的最大亮点,所以一个成熟的功能组件是需要很多付出的,哪怕是一个小功能。关注和使用这个组件的时间超过4年,再次向作者表示感谢。可谓是麻雀虽小五脏俱全。前面已经介绍了,Rank就是相对与所有组合的一个顺序号(升序),而上面介绍的都是通过IEnumerable来一次获取所有组合,但如果只需要获取指定位置的组合咋办,看代码:

//初始化一个组合,从6个数中,选择4个的所有组合中,取位置2的组合(从0开始)
var cn = new Combination (choices:, picks:, rank:);
Console.WriteLine ("{0} n={1}, k={2}, rank={3}\n", cn, cn.Choices, cn.Picks, cn.Rank); //设置Rank为-1,默认取最后一个位置的组合
cn.Rank = -;
string text = cn.ToString() + " n=" + cn.Choices + ", k=" + cn.Picks + ", last=" + cn.Rank;
Console.WriteLine (text); //将当前Rank+1,的组合
cn.Rank = cn.Rank + ;
Console.WriteLine ("\n{0} n={1}, k={2}, rank={3}", cn, cn.Choices, cn.Picks, cn.Rank);

结果如下,对比结果和代码,应该很容易理解:

 { , , ,  }  n=, k=, rank=

 { , , ,  }  n=, k=, last=

 { , , ,  }  n=, k=, rank=

同样,还可以通过Picks属性来获取每一个组合中所有的元素,如:

 for (int i = ; i < cn.Picks; ++i)
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

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

上一篇:【原创】开源.NET排列组合组件KwCombinatorics使用(三)——笛卡尔积组合


下一篇:HDU 4045 Machine scheduling (组合数学-斯特林数,组合数学-排列组合)