模板
教程
环境
性能
功能
管理
使用组合改进软件测试用例的生成
测试已经成为软件开发过程中一个至关重要的部分，但近来有三个因素使之扮演了一个甚至更加重要的角色。第一，Microsoft®.NET 开发环境的 诞生戏剧性地改进了开发人员编写定制测试自动化的能力。那些在 .NET 框架面世以前需要花费数周时间创建的测试程序现在仅用几小时就可以写好。第二，正在建立的日益复杂的系统需要更精益求精的测试。最后，软件安全在软件开发过程中已不再是事后才 关注的事情，它已成为一个绝对要素。曾经一度推出可能没有经过完全测试的产品，但这已不再是一个生存选择。为了帮助你迎接当今测试的挑战，本专栏将在随后几个月的 内容里讨论一些关于软件测试的原则、技巧和最佳实践。
本月我将从组合在软件测试中的作用讲起。通过编程产生组合的能力使你能有一种强有力的方法来生成测试用例输入。为了弄清楚什么是组合，现在假定你正在写一个扑克 牌游戏程序。用手工生成所有可能的五张套测试输入将是一件令人很不爽的事情。但是用本文的示例代码，你便可以在分分钟内做好它：
注意你必须选择10个字符，同时每个字符必须来自于20个分类中的一个。因此你要一次从20条中选出10个，或 Choose(20,10)——这个函数我将在本 文稍后讨论。注意我已经简化了这个场景。在实践中，你可能还需要综合考虑每一组合的排列以及边界条件和许多其它测试概念。
在此我将用 C# 建立一个组合类，并示范如何使用组合提高测试效果。我想你会发现理解和应用组合及其相关算法是很有裨益的。
Figure 1 组合演示
屏幕的截屏是最佳示范方式。Figure 1 是一个基于 Windows® 的应用程序屏幕，它演示了组合的使用。正如你所看到的，条目（items）的组合是这些条目的一个子集，它们的顺序并不重要。在这个例子中我有5个条目——名字 分别为 Adam、Barb、Carl、Dave 和 Eric，——而我感兴趣的是大小为3的组合。这里5选3有10种可能的子集：
注意既然顺序并不重要，那么我不考虑 { Carl, Barb, Adam } 这样的子集，因为我认为它和 { Adam, Barb, Carl } 是相同的。Figure 1中所示的例子除了生成组合外，还举例说明了，我需要计算一个特定大小的条目集和子集能有多少种组合。
数学上的组合是对这种子集思路的概括。取代了任意条目的子集的情况，序列n的一个数学组合是从0到n-1的整数的一个子集。因此一次从4个条目中取2个的数学组合 结果是6个元素（译注：element为组合中的一组）：
{ 0, 1 }{ 1, 2 }
{ 0, 2 } { 1, 3 }
{ 0, 3 } { 2, 3 }
正如我所说的，组合在软件测试自动化、开发、管理等的方方面面有着非常重要的作用。虽然组合背后的数学概念是古老而艰深，我最近发现，从一般意义上来说，组合 的概念并没有被软件工程师们很好地理解，同时，那些可以在 Internet 上获得的与组合有关的代码例子多半都是非常低效的，或者在许多情况下，简直就是错误的。
组合
数学组合的三个基本操作如 Figure 2 所示。输出告诉你当 n = 4，k = 2 时，有六种组合：
{ 0, 2 } { 1, 3 }
{ 0, 3 } { 2, 3 }
从这个例子你可以看到我需要建立某种组合，给定条目总数和子集大小来计算全部组合元素的总数，并且确定某个特定组合元素的后继者以便我能列出所有组合元素。
稍微细致地考察这些例子，你可以看到组合有两个重要的特性：条目的总数（数学上通常用 n 表示）和子集的大小（通常用 k 表示）。数学组合可以是 0 基 （0-based）或 1 基（1-based）的。我将在这个专栏中通篇使用 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 与 Choose 函数中的 n 和 k 是非常容易混淆的。n = 7，k = 4 的数学组合（在7个条目中一次取4个） ，其中有象 { 0, 3, 4, 6 } 这样的元素，而 Choose(7,4) 函数则返回 35，这是从7个条目中一次取4个的组合元素总数。
组合经常会和排列搞混淆，排列是一组条目所有的可能排列，这时顺序是重要的。如果说你有姓名 Alex、Bill、Cris 和 Doug。用词典顺序排列的 话，前三个排列是：{ Alex, Bill, Cris, Doug },{ Alex, Bill, Doug, Cris } 和 { Alex, Cris, Bill, Doug }。
一个组合类
数学组合非常适宜用一个类来实现。你需要数据成员存储 n 的值（条目总数），k（每个子集元素的条目个数）的值，以及一个数组来保存每个组合元素的“原子”。Figure 3 是表述某个Combination（组合）对象的基本代码和创建该组合对象第一个词典元素的构造函数，以及将它表示为一个字符串的代码。我决定使用C#，但你可以 轻松地将它改编为你所选的任意一种基于 .NET的编程语言。
我将这个代码放入类库（Class Library）编译后，我可以给它增加一个工程选项参数（Project Reference），并从 .NET 控制台 程序调用它，就象我在此所做的这样：
Console.WriteLine("\nCombination c(5,3) is initially " + c.ToString()); 下面的输出将显示在屏幕上：Combination c(5,3) is initially { 0 1 2 }
当组合类的构造函数进行如下调用时:Combination c = new Combination(5,3);
我在内存中获得一个对象，它表示五个条目中一次取三个的最初的词典排序的数学组合元素。内存中的对象可以被表示为如 Figure 4 所示。
Figure 4 内存中的对象
构造函数代码创建最初的组合元素时是相当简单的。两个代表条目总数和子集大小的参数被分别存储在数据成员 n 和 k 中。因为我处理的数值可能会很大， 所以我决定使用 C# 的 long 类型代替int 类型。如果我愿意的话，我可以用 ulong 类型（无符号 long）获得双倍的数值范围。我用子集的大小 k 来为一个 long 类型的命名数组分配空间，然后用 0 到 k-1 范围的整数填充每个数据单元。
计算组合元素的个数
现在我已经确定了如何创建一个组合对象，让我们看看组合的三个基本操作的第二个——根据某个给定的条目总数 n 及子集大小 k 来计算组合元素的总数。举个例子，如果你处理一次从 n＝5 条目中取 k＝3，这里有10种可能的组合元素：
{ 0, 1, 3 } { 1, 2, 3 }
{ 0, 1, 4 } { 1, 2, 4 }
{ 0, 2, 3 } { 1, 3, 4 }
{ 0, 2, 4 } { 2, 3, 4 }
我想实现一个 Choose(n,k) 函数，它返回组合元素的个数；Choose(5,3) 返回10。查找现有的Choose 实现，我惊讶地发现 Internet 上的大多数算法都很不耐用。在我向你展示我的 Choose 实现之前，让我们简要地审视一下 Choose 函数的标准实现。
编写 Choose(n,k) 函数的标准方法是直接使用其定义公式。这是一个明显的但是拙劣解决方案。这里是一个用 C# 编码的典型 Choose(n,k) 函数 ：
