组合生成器

• 下载源代码 - 11.1 Kb

引言

本文介绍了一个用于生成组合的代码库。“组合”是指输入序列中具有特定长度的子集。例如，给定输入 {1, 2, 3, 4}，请求所有长度为 2 的组合会得到 {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, 和 {3, 4}。从大小为 n 的输入中抽取大小为 r 的组合的数量称为 nCr，等于 n! ÷ [r!(n-r)!]。然而，这个公式只有在输入实际上是一个集合（所有元素都不同）时才正确。我需要一个能够正确处理输入中重复项的算法，而本文中的代码就能做到这一点。巧合的是，每个组合的元素都是以排序的顺序返回的，组合本身也是按顺序返回的。

Using the Code

生成整数集合 {1, 2, 3, 4, 5} 的所有长度为 3 的组合

int[] input = new int[] { 1, 2, 3, 4, 5 };
Combinations<int> combinations = new Combinations<int>(input, 3);
foreach (int[] combination in combinations) 
{
  // Do something with "combination".
}

这将导致 foreach 的主体被执行，其中 combination 被设置为以下值：{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, 和 {3, 4, 5}。

请注意，输入不需要是数组；它可以是 IEnumerable 的任何实现，包括大多数标准的集合类。另外，输入也不一定是 int；只需更改 Combinations 对象上的泛型类型参数，就可以使用任何数据类型。

如果输入包含重复项，它们将被正确处理。例如，以下代码

int[] input = new int[] { 1, 2, 2, 3 };
Combinations<int> combinations = new Combinations<int>(input, 3);
foreach (int[] combination in combinations) 
{
  // Do something with "combination".
}

将产生以下 combination 值：{1, 2, 2}, {1, 2, 3}, {2, 2, 3}。

可以使用替代的 IComparer 进行相等性和排序。例如

string[] input = new string[] { "alpha", "ALPHA", "beta", "gamma" };
Combinations<string> combinations = new Combinations<string>(input,
  StringComparer.CurrentCultureIgnoreCase, 2);
foreach (string[] combination in combinations) 
{
  // Do something with "combination".
}

导致 combination 采用以下值：{"alpha", "alpha"}, {"alpha", "beta"}, {"alpha", "gamma"}, {"beta", "gamma"}。“alpha”和“ALPHA”被视为等价，并且在输入列表中出现（在此情况下为“alpha”）的版本被视为规范形式；输出中只会出现该形式。

当算法只知道 n 值（输入集）但 r 值（输出大小）未知时，可以执行某些过程。这些过程实际上是在 ElementSet 类中执行的。ElementSet 由接受 IEnumerable 的两个 Combinations 构造函数内部构造，但也可以单独构造 ElementSet 并将其传递给 Combinations 构造函数。如果将相同的输入处理多个输出长度，则此方法很有用。例如

int[] input = new int[] { 1, 2, 3, 4, 5 };
ElementSet<int> elements = new ElementSet<int>(input);
for (int i = 0; i <= 5; i++) {
  Combinations<int> combos = new Combinations<int>(elements, i);
  foreach (int[] combo in combos) 
  {
    // Do something with "combo".
  }
}

此代码将有效地生成 {1, 2, 3, 4, 5} 的所有子集。任何不依赖子集长度的处理都发生在循环外部。此外，此示例表明 r=0 和 r=n 的边缘情况也得到了正确处理。在 r=0 的情况下，会返回一个长度为零的单个数组；在 r=n 的情况下，会返回一个包含整个输入的单个数组。

可以使用自定义 IComparer 和预先构造的 ElementSet。IComparer 必须与输入数据一起传递给 ElementSet 构造函数。在这种情况下，IComparer 不会传递给 Combinations 构造函数。

复杂度分析

在本讨论中，n 是输入的大小，r 是输出的大小，m 是输入中“不同”元素的数量。

循环

ElementSet 构造函数

假设传递给构造函数的 IEnumerable 可以在可忽略的时间内枚举其内容，则构造函数的操作复杂度为 O(nlog₂n)。

Combinations 构造函数

给定一个已构造的 ElementSet，复杂度为 O(1)；否则，复杂度为 O(nlog₂n)。

Combinations.GetEnumerator()

O(r)

IEnumerator.Reset()

O(r)

IEnumerator.Current (get)

O(r)

IEnumerator.MoveNext()

O(r×m)

存储

此处仅提及大量的存储空间。

ElementSet<T>

• 大小为 m 的 SortedList<T, int>
• int[r]
• 大小为 m 的 SortedDictionary<T, int>（仅在构造期间）

Combinations<T>

此类没有重要的存储需求。

IEnumerator<T[]>

• int[r]
• int[m]
• T[r]（仅在调用 Current 属性的 getter 时）
• 递归的堆栈空间，深度为 O(r)（仅在调用 MoveNext() 时）

诊断

源存档包含一个解决方案，其中包含两个项目和三个配置。“Test”配置下，只有“Combinations”项目会被构建，并且 13 个 NUnit 测试将被编译到程序集中。“Debug”和“Release”配置下，“Combinations”项目的测试用例不会被编译，而“Benchmark”项目会被编译，它提供了一个简单的控制台模式基准测试程序，用于测试该库。在 1.7GHz 处理器上以发布模式进行的基准测试，对于从 10 个不同元素的集合中选择 3 个整数的集合，每秒可生成超过四百万个组合；而对于从包含 10% 重复项的 1000 个元素的集合中选择 700 个整数的集合，每秒可生成 66,571 个组合。输入和输出的大小对基准测试的影响远大于重复项的百分比。还提供了构造 ElementSet 的基准测试，分别使用升序和随机顺序的整数数组作为输入。我的数据范围是从大约每秒 150 万个输入元素（对于 10 个整数的数据集）到大约每秒 50 万个输入元素（对于 1000 个整数的输入）。升序与随机排序无关紧要。

工作原理

ElementSet 构造函数首先收集所有输入元素。它会填充一个 SortedList<T, int>，其中每个键映射到它出现的次数。实际上，它会先填充一个 SortedDictionary，然后复制到 SortedList，因为这种方法能获得更好的复杂度。此外，ElementSet 会对元素进行反向累积求和，将值存储在 int[] 中，这样就可以在 O(1) 的时间内确定在列表中给定位置及之后有多少个元素（非不同元素）。这在后面会用到。

Combinations 类除了包含一个 ElementSet 和 r 值之外，几乎不做任何事情。所有工作都在 IEnumerator 中完成。

IEnumerator 使用“索引”来生成组合。想象一下所有输入元素从左到右排列，重复项堆叠在彼此上方，索引最初尽可能地“推”到左边，使得每个索引指向它自己的元素（非不同元素）。移动到下一个值包括将一个索引滑动到右边。如果它滑出边缘或碰到另一个索引，则下一个索引向右移动一个元素，并且当前索引被推回左边，直到它碰到另一个索引。一旦所有索引都向右移动到可能的最大位置，就没有更多组合可以生成了。其他代码用于确保索引永远不会向右移动得太远，以至于没有留下足够的空间给它右边的其他索引；这就是使用反向累积求和的原因。一旦索引确定了它们的位置，在 Current 属性的 getter 中，通过依次用每个索引索引 SortedList<T, int>.Keys 集合，并将值存储到数组中来生成组合。

其他类似代码

已经有一篇 Combinatorial Algorithms in C# 的文章，其中包含一个组合算法（以及其他算法），但该算法在遇到输入中的重复项时似乎会失败。对我来说，这是一个问题。另外，该文章的代码实现了 IEnumerator，而我的代码实现了 IEnumerable；因此我的代码可以在 foreach 中使用，但另一篇文章的代码不能。gybrush 的解释是“如果你之前已经请求过对同一个序列的枚举器，它不能失效，因为它可能仍在被使用。这在当前的 Combinatorial 类实现中是不可能的，而且我看不到轻松修改它的方法。” 而我的算法则清晰地区分了代码，使得支持多个 IEnumerator 变得容易。最后，我的代码是泛型的，因此以类型安全的方式生成组合。