生成所有组合元素

　  组合的第三个基本操作是根据给定条目个数 n 和子集大小 k 生成一个所有组合元素的清单。正如前面所示的 Choose 函数的问题一样，Internet 上找到的 并不是经典方案。让我们简单看看一个典型的情况：给定 n 和 k 值，生成所有组合元素的解决方案，并且我将改进它。

　  假定你有四个姓名条目——Adam, Barb, Carl, Dave——你想得到所有这四个条目中每次选出两个元素的组合。下面所示的 C# 代码片断将生成这个组合的六个元素：

　  但是这里有三个问题。首先，如果你想要生成组合的所有元素时，这个方法运行很正常，但是如果你只想得到部分元素或一个特别元素呢？第二，这是一个对于特定问题的特定 解法，它并不具有普遍性。第三，只有当每个子集元素的条目个数 k 很小时，它才能工作得较好。

　  但是如果 k 非常大时会怎样呢？如果你想一次从 n = 100 个的条目中挑出 50 个，你就不得不编写50个循环或使用递归。

　  对于生成所有组合元素的一个更好的解决方案是实现一个 Successor（继承）方法，它返回给定元素的下一个按词典排序的元素。如果你将 Successor 和 ApplyTo 方法联合使用，它 将某个数学组合映射到一个字符数组上，你将会具备一个有效的、具有普遍性的方法来生成所有组合元素。

　  Figure 6 的代码表示了 Successor 方法。Successor 一开始就检查这里是否存在下一个组合元素。举个例子，假设你正在处理每次从 n＝5 个条目中取 k＝3 个元素。这里 有 10 种组合情况：

　  注意你可以确定词典序列的最后一个元素，{ 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 方法很简单：

　  通过对字符串数组输入参数的检查，确保字符串个数的正确性之后，用子集 k 的大小创建一个结果数组。然后遍历输入字符串 ，并将一个引用存储到结果数组相应的单元中。与组合所实现的许多操作一样，如果你不从头到尾跟踪一两个例子，所发生的事情并不是那么显而易见。

　  根据适当的条目数和子集大小实例化一个 Combination 对象之后，创建一个字符串数组来保存结果组合元素。用一个 While 循环来遍历所有组合元素——回想一下我们曾说过，当 不存下一个元素时，Successor 方法返回 null——并且 ApplyTo 方法将当前元素映射到原始字符串数组上。

　  结束语

　  在计划和进行配置测试的过程中，组合是一个不可或缺的工具，尤其是在被称为交互式分析的子领域里。举个例子，假设你需要在一台安装了多个浏览器和多媒体播放器 的机器上测试产品。你想要从八个浏览器集合中选装三个浏览器，从六个多媒体播放器集合中选装两个播放器来进行系统结合测试。这里有多少配置的组合呢？你怎样才能 编写程序列出这些配置？本文呈现的技术使得你很容易就计算出有 Choose(8,3) * Choose(6,2) = 840 个可能的测试配置。它也让你很容易编程列出所有这些配置。

　  在检查和测试执行路径时，组合是很有用的。我将用一个经典的问题来举例说明，它是一个分析执行路径的代理（微软常用这种例子问题来对测试工程师候选 人进行面试）。假设你在开发一个游戏。玩家进入一个铺了地板砖的房间的西南角。玩家必须通过移动一块地砖到东边或移动一块地砖到北边以便自己移动到房间的东北角（换句话说玩家总是向出口方向移动并且不能 走回头路）。如果这个房间很小－只有 10 块地砖长 6 块地砖那么宽——玩家会有多少种不同的路径走法？你能测试所有这些路径吗？如果移动到东边用字母 E 代表而移动到北边用字母 N 代表，一个到出口的可能路径就是玩家先向东移动所有步然后一直向北：

　  注意这里玩家无论怎么移动，总是恰好只有16步。还要注意你可以认为移动一步为“E”或“not E”。如果你想象16格的一个序列，你必须用“E”填满16格中的10格 （因为剩下的格子一定为“N”）。因此，这个问题的答案是这里有 Choose(16,10) = 8,008 个可能路径，并且你可以用本文示例代码轻松地生成它们。

　  正如我早先说过的，测试是软件开发的一个极其重要的方面。下次还是在这里，我将给你提供更多的技巧应用到你的测试过程中。