组 合
在图2中描述了数学组合中的三个必要操作，输出的结果会告诉你，当n=4，k=2时共有6中组合：
| { 0, 1 } { 1, 2 } { 0, 2 } { 1, 3 } { 0, 3 } { 2, 3 } |
从这个例子可以看出，给定了集合中元素的数量，以及子集的大小，我们就能够计算出一共有多少种组合，并列举出所有的组合情况。
图2 组合：
| static void Main() { long n = 4; long k = 2; Console.WriteLine("With n = " + n + ", and k = " + k); Console.WriteLine("There are " + Combination.Choose(n,k) + "combinations\n"); Combination c = new Combination(n,k); Console.WriteLine("The mathematical combinations are:"); while (c != null) { Console.WriteLine(c.ToString()); c = c.Successor(); } Console.ReadLine(); } |
仔细观察，你会发现组合有两个重要的参数：集合中元素的数量（数学中常常用n来表示）和子集的大小（常常用k表示）。组合在数学领域中有0型组合和1型组合。接下来的例子我所指的都是0型组合，并用我们所熟知的n、k来表示。
在我之前例子中的组合都是用字典序枚举的。在数学的整型数中，这种排序即为递增的排序。例如当n=5，k=3时，组合的第一个元素是{0，1，2}，下一个元素是{0，1，3}，因为12在13之前。
组合中的一个重要函数是根据n和k计算出不同组合的总个数。这个函数常叫做Choose。因此在最开始5个人名的例子中，我们可以表示为Choose(5,3)=10，这表示从5个元素中一次选3个，共有10种不同的组合。你可能会看见有许多其他的函数名表示同样的意思，但这边文章里我都用Choose来表示。
Choose函数中的n和k很容易被人混淆。一种数学中的组合n=7，k=4（7个元素一次选4个）的其中一种组合便是{0，3，4，6}，而Choose(7,4)返回值则是35。
人们常常把组合与排列混淆，排列是一个有序的集合，在排列中{Alex，Bill，Cris，Doug}，{Alex，Bill，Doug，Cris}和{Alex，Cris，Bill，Doug}是不同的集合。
组合类
数学中的组合能够很漂亮的被描述为类。首选你需要定义n和k，以及一个元素的数组。在图3中我们定义了组合的一些基本元素，其中构造函数用递增的长整型整数初始化了data元素数组。我建议你使用C#语言，但你也可以用.Net平台的其他语言，转换是很容易的。
图3 组合类的定义
| public class Combination { private long n = 0; private long k = 0; private long[] data = null; public Combination(long n, long k) { if (n < 0 || k < 0) // normally n >= k throw new Exception("Negative parameter in constructor"); this.n = n; this.k = k; this.data = new long[k]; for (long i = 0; i < k; ++i) this.data[i] = i; } public override string ToString() { StringBuilder sb = new StringBuilder(); sb.Append("{ "); for (long i = 0; i < this.k; ++i) sb.AppendFormat("{0} ", this.data[i]); sb.Append("}"); return sb.ToString; } |
