分类： C/C++
2008-04-03 17:29:53
string[] deck = new string[] { "Ac", "Ad", "Ah", "As", "Kc", (...) };
Combination c = new Combination(52,5); // 52 cards, 5 at a time
string[] pokerHand = new string[5];
while (c != null)
{
pokerHand = c.ApplyTo(deck);
PrintHand(pokerHand);
c = c.Successor();
} 一旦你谙熟组合之道，它在许多测试自动化场合极其有用。另外有一个例子，假定你正在测试某个系统，接收用户输入到一个容纳10个字符的文本框（textbox）。输入可能是“ABCDEFGHIJ”，同时另一个可能是“!@#$%^&*()”。你想知道这里有多少个不同的测试用例。让我们假设你已决定让字符输入 含在20个等价类中——也就是你的系统所关心的等价分类范畴。一个等价类可能是大写字母A到Z，而另一个等价类可能是数字0到9。
屏幕的截屏是最佳示范方式。Figure 1 是一个基于 Windows® 的应用程序屏幕，它演示了组合的使用。正如你所看到的，条目（items）的组合是这些条目的一个子集，它们的顺序并不重要。在这个例子中我有5个条目——名字 分别为 Adam、Barb、Carl、Dave 和 Eric，——而我感兴趣的是大小为3的组合。这里5选3有10种可能的子集：
{ Adam, Barb, Carl }, { Adam, Barb, Dave }, . . . { Carl, Dave, Eric }
注意既然顺序并不重要，那么我不考虑 { Carl, Barb, Adam } 这样的子集，因为我认为它和 { Adam, Barb, Carl } 是相同的。Figure 1中所示的例子除了生成组合外，还举例说明了，我需要计算一个特定大小的条目集和子集能有多少种组合。 { 0, 1 }{ 1, 2 }
{ 0, 2 } { 1, 3 }
{ 0, 3 } { 2, 3 }
正如我所说的，组合在软件测试自动化、开发、管理等的方方面面有着非常重要的作用。虽然组合背后的数学概念是古老而艰深，我最近发现，从一般意义上来说，组合 的概念并没有被软件工程师们很好地理解，同时，那些可以在 Internet 上获得的与组合有关的代码例子多半都是非常低效的，或者在许多情况下，简直就是错误的。
组合
数学组合的三个基本操作如 Figure 2 所示。输出告诉你当 n = 4，k = 2 时，有六种组合：
{ 0, 1 } { 1, 2 }
{ 0, 2 } { 1, 3 }
{ 0, 3 } { 2, 3 }
从这个例子你可以看到我需要建立某种组合，给定条目总数和子集大小来计算全部组合元素的总数，并且确定某个特定组合元素的后继者以便我能列出所有组合元素。 一个组合类
数学组合非常适宜用一个类来实现。你需要数据成员存储 n 的值（条目总数），k（每个子集元素的条目个数）的值，以及一个数组来保存每个组合元素的“原子”。Figure 3 是表述某个Combination（组合）对象的基本代码和创建该组合对象第一个词典元素的构造函数，以及将它表示为一个字符串的代码。我决定使用C#，但你可以 轻松地将它改编为你所选的任意一种基于 .NET的编程语言。
我将这个代码放入类库（Class Library）编译后，我可以给它增加一个工程选项参数（Project Reference），并从 .NET 控制台 程序调用它，就象我在此所做的这样：
Combination c = new Combination(5,3);下面的输出将显示在屏幕上：
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, 2 } { 0, 3, 4 }
{ 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) 函数 ：
// poor implementation of Choose(n,k)
static int Choose(int n, int k)
{
int numerator = Factorial(n);
int denominator = Factorial(k) * Factorial(n-k);
return ( numerator / denominator );
} 辅助函数 Factorial 的实现如下： static int Factorial(int m)
{
int ans = 1;
for (int i = m; i >= 1; —i)
{
ans = ans * i;
}
return ans;
}
这里的 Choose(n,k) 实现有几个问题：最严重的是它会因为当 n 和 k 的值十分小时而溢出。注意这个 Choose(n,k) 首先计算 Factorial(n)， 即便 n 是一个很小的值，它也会迅速增大到一个非常大的数 ( 比如，21! 将溢出一个无符号的 64 位数)。其次 Choose(n,k) 的值由两个阶乘的乘积 来除，这也可能成为一个非常大的数，得出的结果可能非常小。关键是即使 Choose(n,k) 返回的结果很小，中间计算结果很容易溢出。
一个更好的 Choose(n,k) 实现使用一个不同的方法计算其答案。改版的 Choose(n,k) 使用以下不同的公式来计算：
Choose(n,k) = (n * (n-1) * (n-2) * ... * (n-k+1)) / ( 1 * 2 * ... * k)这个算法看起来很丑，但用一个例子来说明就知道，它更容易理解：
Choose(7,3) = (7 * 6 * 5) / (1 * 2 * 3)
这个算法取代了原来计算分子（一个大数），然后计算分母（一个大数），然后相除，你可以计算部分乘积法并随意进行除法运算。对于 Choose(7,3) 例子，你 先计算 7 * 6 并除以 2，得到 21（译注：原文为“getting 24”显然不对，7 * 6/2＝21）(跳过此分数下面部分的第1项，因为被1除是没有作用的)。这时用5乘以部分乘积并用3除，你可以得到答案35， 和前面的结果一样。
这里对 Choose(n,k) 的第二次优化是由以下特性产生的：
Choose(n,k) = Choose(n, n-k).举个例子，Choose(10,8) = Choose(10,2)。这不是一个明显的关系，但是如果你用一些例子来试验的话，你将看到为什么这是对的。直接计算 Choose(10,8) 之间涉及到计算七个部分乘积和七个除法，但是计算等价的 Choose(10,2) 只要求一个乘法和一个除法操作。
生成所有组合元素
组合的第三个基本操作是根据给定条目个数 n 和子集大小 k 生成一个所有组合元素的清单。正如前面所示的 Choose 函数的问题一样，Internet 上找到的 并不是最优方案。让我们简单看看一个典型的情况：给定 n 和 k 值，生成所有组合元素的解决方案，并且我将改进它。
假定你有四个姓名条目——Adam, Barb, Carl, Dave——你想得到所有这四个条目中每次选出两个元素的组合。下面所示的 C# 代码片断将生成这个组合的六个元素：
// naive technique to generate all combinations
Console.WriteLine("\nAll elements of 4 names, 2 at a time: ");
string[] names = {"Adam", "Barb", "Carl", "Dave"};
for (int i = 0; i < names.Length; ++i)
{
for (int j = i+1; j < names.Length; ++j)
{
Console.WriteLine( "{ " + names[i] + ", " + names[j] + " }" );
}
}
如果你执行这个代码，（正确的）结果将是：
{ Adam, Barb }, { Adam, Carl }, { Adam, Dave }, { Barb, Carl },
{ Barb, Dave }, { Carl, Dave }.
但是这里有三个问题。首先，如果你想要生成组合的所有元素时，这个方法运行很正常，但是如果你只想得到部分元素或一个特别元素呢？第二，这是一个对于特定问题的特定 解法，它并不具有普遍性。第三，只有当每个子集元素的条目个数 k 很小时，它才能工作得较好。
但是如果 k 非常大时会怎样呢？如果你想一次从 n = 100 个的条目中挑出 50 个，你就不得不编写50个循环或使用递归。
对于生成所有组合元素的一个更好的解决方案是实现一个 Successor（继承）方法，它返回给定元素的下一个按词典排序的元素。如果你将 Successor 和 ApplyTo 方法联合使用，它 将某个数学组合映射到一个字符数组上，你将会具备一个有效的、具有普遍性的方法来生成所有组合元素。
Figure 6的代码表示了 Successor 方法。Successor 一开始就检查这里是否存在下一个组合元素。举个例子，假设你正在处理每次从 n＝5 个条目中取 k＝3 个元素。这里 有 10 种组合情况：
{ 0, 1, 2 } { 0, 3, 4 }
{ 0, 1, 3 } { 1, 2, 3 }
{ 0, 1, 4 } { 1, 2, 4 }
{ 0, 2, 3 } { 1, 3, 4 }
{ 0, 2, 4 } { 2, 3, 4 }
注意你可以确定词典序列的最后一个元素，{ 2, 3, 4 }，因为这里只有一个元素它有第一个原子2——它等于 n－k 的值，或者换句话说，它有一个 n-k 的值在第0个位置上。这个关系一般来说对于所有的组合都是正确的。同样地，你可以确定词典序列的第一个元素，{ 0, 1, 2 }，因为这里只有一个元素的最后一个原子为 2，或者换句话说，这里有 n-k 的值在第 k－1 位置上。而且，一般来说这总是正确的。如果这里没有有效的下一个元素 Successor 方法就返回 null。选择返回 null 将导致抛出一个异常或返回一个错误代码。
生成 Successor 元素的算法没有使用任何特别的技巧。实质上你从最右边的元素开始向左移动直到你定位于应该增加的最左边的原子。这时你以索引 i 增加原子并重新安排所有原子到 i 的右边比左边的值大 1。举个例子，设 n = 5 和 k = 3 并且你想得到组合{ 0, 3, 4 }的后继者。索引 i 开始于地址 2（指向值为 4 的原子），并且左移直到它到地址 0（指向值为 0 的原子）。原子值被加1，并且右边（3 和 4）的所有原子从数组左边的值增加，得到结果{ 1, 2, 3 }。
一旦你有了 Successor 方法，便需要一个 ApplyTo 方法，它将某个组合元素放到一个字符串数组中。ApplyTo 方法很简单：
public string[] ApplyTo(string[] strarr)
{
if (strarr.Length != this.n)
throw new Exception("Bad array size");
string[] result = new string[this.k];
for (long i = 0; i < result.Length; ++i)
result[i] = strarr[this.data[i]];
return result;
}
通过对字符串数组输入参数的检查，确保字符串个数的正确性之后，用子集 k 的大小创建一个结果数组。然后遍历输入字符串 ，并将一个引用存储到结果数组相应的单元中。与组合所实现的许多操作一样，如果你不从头到尾跟踪一两个例子，所发生的事情并不是那么显而易见。
根据适当的条目数和子集大小实例化一个 Combination 对象之后，创建一个字符串数组来保存结果组合元素。用一个 While 循环来遍历所有组合元素——回想一下我们曾说过，当 不存下一个元素时，Successor 方法返回 null——并且 ApplyTo 方法将当前元素映射到原始字符串数组上。
结束语
在计划和进行配置测试的过程中，组合是一个不可或缺的工具，尤其是在被称为交互式分析的子领域里。举个例子，假设你需要在一台安装了多个浏览器和多媒体播放器 的机器上测试产品。你想要从八个浏览器集合中选装三个浏览器，从六个多媒体播放器集合中选装两个播放器来进行系统结合测试。这里有多少配置的组合呢？你怎样才能 编写程序列出这些配置？本文呈现的技术使得你很容易就计算出有 Choose(8,3) * Choose(6,2) = 840 个可能的测试配置。它也让你很容易编程列出所有这些配置。
在检查和测试执行路径时，组合是很有用的。我将用一个经典的问题来举例说明，它是一个分析执行路径的代理（微软常用这种例子问题来对测试工程师候选 人进行面试）。假设你在开发一个游戏。玩家进入一个铺了地板砖的房间的西南角。玩家必须通过移动一块地砖到东边或移动一块地砖到北边以便自己移动到房间的东北角（换句话说玩家总是向出口方向移动并且不能 走回头路）。如果这个房间很小－只有 10 块地砖长 6 块地砖那么宽——玩家会有多少种不同的路径走法？你能测试所有这些路径吗？如果移动到东边用字母 E 代表而移动到北边用字母 N 代表，一个到出口的可能路径就是玩家先向东移动所有步然后一直向北：
E E E E E E E E E E N N N N N N一个不同的路径是：
E N E N E N E N E N E N E E E E注意这里玩家无论怎么移动，总是恰好只有16步。还要注意你可以认为移动一步为“E”或“not E”。如果你想象16格的一个序列，你必须用“E”填满16格中的10格 （因为剩下的格子一定为“N”）。因此，这个问题的答案是这里有 Choose(16,10) = 8,008 个可能路径，并且你可以用本文示例代码轻松地生成它们。