生成所有的组合元素
第三个优化是处理生成组合元素的函数。网络上的这类函数都缺乏效率，我们下面就简单地看看一个典型的生成组合的方法，然后我再优化它。
假如你有4个元素——Adam，Barb，Carl，Dave——从中一次选取2个，输出所有的组合元素。代码如下：
| // 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很大呢？如果是要从 100个元素中选取50个，你将不得不做50次代码循环或者是递归。
Successor函数是一个生成组合的更好的解决方案，它它只根据给定的组合元素生成下一个组合元素。如果你结合Successor函数和ApplyTo函数来生成组合，将会变得非常高效。
图6是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 } |
图6 元素的字典下一个组合
| 请public Combination Successor() { if (this.data.Length == 0 || this.data[0] == this.n - this.k) return null; Combination ans = new Combination(this.n, this.k); long i; for (i = 0; i < this.k; ++i) ans.data[i] = this.data[i]; for (i = this.k - 1; i > 0 && ans.data[i] == this.n - this.k + i; --i); ++ans.data[i]; for (long j = i; j < this.k - 1; ++j) ans.data[j+1] = ans.data[j] + 1; return ans; } |
请注意，我们都知道组合字典的最后一个元素是{2，3，4}，因为只有这个元素的开头是数字2，2刚好是等于n-k的，也就是说，在位置0有值n-k。这个结果是对所有组合都成立的。同样，你可以知道组合字典的第一个元素是 {0，1，2}，因为只有这个元素的末尾是数字2，也就是说，在k-1的位置有值k-1，同样这个结果是具有普遍性的。Successor函数会在找不到下一个组合元素时返回空值。
