这个Successor函数并没有用什么特别的技巧,我们只是从元素的最右边位置开始做递增地改变,直到最后改变到最左边的元素。每一次改变,我们都从位置i开始递增,然后重置i右边的所有元素,重置的方法是该位置的值比它左边一个位置的值大1。 举个例子,当n=5,k=3时,你想得到组合{0,3,4}的下一个组合元素。索引i从位置2开始(位置2指向的值是4),然后索引左移直到位置0(位置0指向的值是0)。0位置的值增加到1,然后位置在它右边的所有值(3和4)都比左边的大1,因此得到结果{1,2,3}。
有了Successor函数还不够,你还需要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的result字符串数组,该数组为传入的数组的每个位置存储了引用。如果还不理解,就自己运行程序调试跟踪吧~~~
在创建了一个组合实例后,我们创建了一个字符串数组来保存组合结果。用一个while循环遍历所有的组合元素——直到Successor方法返回null,表示组合元素遍历完成——然后ApplyTo函数映射对应元素的值。
结 论
组合在规划和执行配置的测试中有着不可替代的作用,特别是在一些互动分析的分支领域。假如你需要在一台机器上测试多种浏览器和媒体播放器来安装你的产品,你想要你的系统从8种浏览器中选择3种安装,并从6个媒体播放器中选择2 个安装,一共有多少种可能的配置?你能否用程序列举出所有的配置?本文的程序能够让你轻松得到结果: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”和“非 E”两种。你可以在脑海中构造一个16个连续的空格,你必须要在这16个空格中填充入10个“E”(因为剩下的必须填“N”)。所以,这个问题的答案便是 Choose(16,10)=8080种可能的路径,你可以通过本片的代码轻松得到结果。
正如我之前所说,测试在软件开发中具有非常重要的作用,跟着我一起,你可以把这些优化加入在你的测试过程中。
原文作者:Dr. James McCaffrey
英文原文:http://msdn.microsoft.com/zh-cn/magazine/cc163957(en-us).aspx