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

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

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

前言

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

1.Permutation类基本介绍

  Permutation类是根据指定的对象列表,选择一些不同的对象形成一个排列,排列是有顺序的,而且每一次不重复选择同一个对象。其实有了第一篇的基础,这个类的使用也很简单,还是先看看Permutation类的初始化,几个主要的构造函数如下:

1 Permutation()//Make an empty Permutation.  
2 Permutation(Int32)//Make a new Permutation of all the supplied number of choices with a Rank of 0.  
3 Permutation(Int32[])//Make a new Permutation from the supplied elements.  
4 Permutation(Permutation)//Make a copy of a Permutation.  
5 Permutation(Int32,Int32)//Make a new Permutation with picks number of elements taken from a possible number of choices of Rank 0.  
6 Permutation(Int32[],Int32)//Make a new Permutation from the supplied elements taken from the available number of choices.  
7 Permutation(Int32,Int32,Int64)//Make a new Permutation with picks number of elements taken from a possible number of choices of the supplied rank.  

参数主要有下面几个注意点,参数的意义和Combination类似:

choices:可供选择的数的个数,如果不提供实际的源数据source,默认就是从0开始的整数;
picks:要选择组合序列的个数
source:可以直接用初始化列表,而不是固定的从0开始
rank:这个属性是我认为使用这个组件最强大的地方,因为是按照升序生成所有的组合序列, 而rank就是指定你要选择的在整个组合序列中当前rank位置的组合序列。

下面用几个例子说明几个主要方法的使用情况。

2.获取所有N选K的排列列表

设从{0,1,2}3个元素中,每次取2个的排列,所有的排列情况有哪些呢?直接上代码,比较容易看得懂:

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

运行结果如下:

1 n=3 , picks=2
2  0:  { 0, 1 }
3  1:  { 0, 2 }
4  2:  { 1, 0 }
5  3:  { 1, 2 }
6  4:  { 2, 0 }
7  5:  { 2, 1 }

  同理,要获取当前数据源,所有可能的组合情况呢,Permutation也提供了GetRowsForAllPicks方法,看代码:

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

结果:

 1 n=3 , picks=2
 2  0:  { 0 }
 3  1:  { 1 }
 4  2:  { 2 }
 5  0:  { 0, 1 }
 6  1:  { 0, 2 }
 7  2:  { 1, 0 }
 8  3:  { 1, 2 }
 9  4:  { 2, 0 }
10  5:  { 2, 1 }

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

  上述例子很清楚的说明了N选K的排列情况,和前面组合的情况一样,Permutation也提供了Permute的方法,将排列的情况与队列列表进行转换,为了简单明了,上代码:
1 var things = new List<object>{"apple","bench","chair"};
2 
3 foreach (var row in new Permutation (things.Count,2).GetRows())
4 {
5     foreach (var mix in Permutation.Permute (row, things))
6         Console.Write ("{0} ", mix);
7     Console.WriteLine ();
8 }

结果如下:

1 apple bench
2 apple chair
3 bench apple
4 bench chair
5 chair apple
6 chair bench

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

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

  这个类也提供了Rank功能,也是需要获取指定位置的排列,为了和组合的对比,我们采用了几乎一样的代码,但参数不一样,看代码和结果就知道了:  

 1 //初始化一个排列,从4个数中,选择2个的所有排列中,取位置2的排列(从0开始)
 2 var pn = new Permutation (choices:4, picks:2, rank:2);
 3 
 4 Console.WriteLine ("{0}  n={1}, k={2}, rank={3}\n", pn, pn.Choices, pn.Picks, pn.Rank);
 5 
 6 //设置Rank为-1,默认取最后一个位置的排列
 7 pn.Rank = -1;
 8 string text = pn.ToString() + "  n=" + pn.Choices + ", k=" + pn.Picks + ", last=" + pn.Rank;
 9 Console.WriteLine (text);
10 
11 //将当前Rank+1,的排列
12 pn.Rank = pn.Rank + 1;
13 Console.WriteLine ("\n{0}  n={1}, k={2}, rank={3}", pn, pn.Choices, pn.Picks, pn.Rank);

结果:

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

5.资源

  资源参考前一篇文章的资源,几乎一样:开源.NET排列组合组件KwCombinatorics使用(一)——组合生成类 

  如果本文资源或者显示有问题,请参考 本文原文地址http://www.cnblogs.com/asxinyu/p/4261451.html

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