C#中的组合算法

• 下载源文件 - 9 Kb

引言

本文将介绍一组可用于对对象集合执行一些基本组合操作的类。这里不会详细解释代码的工作原理，而是主要介绍如何使用这些辅助类。源代码很少（只有 4 个类，4 个文件），如果您想了解算法的实现方式，可以自行查看。

此处显示的实用工具的目的是为程序员提供一种简单的方法来生成对象集合中所有可能的组合、排列和变异。例如，假设您有编号从 1 到 35 的球放在一个黑盒中，想从中取出 5 个。那么从总共 35 个球中取出 5 个球的可能组合大约有 325,000 种。本文介绍的类将生成其中的每一种。这通常非常方便，如果您对黑盒的工作原理有一个理论，并用您的理论测试所有组合，以找出最有可能被抽出的 5 个数字的组合。

详细说明

首先编写

using Combinatorial;

然后声明您的整数数组

Array myIntArray = Array.CreateInstance(
    Type.GetType("System.Int32"), 35);
for (int j = 0; j < myIntArray.Length; j++)
    myIntArray.SetValue(j, j);

然后创建一个组合对象来操作此数组中的对象（在本例中，对象为 System.Int32 类型），如下所示

Combinations combs = new Combinations(myIntArray, 5);

现在编写一个循环来生成从 35 个整数中选择 5 个的所有可能组合。

while(combs.MoveNext()) {

    Array thisComb = (Array)combs.Current;

    for (int i = 0; i < thisComb.Length; i++) {
        // Just access the value. This requres boxing.
        int nVal00 = (int)thisComb.GetValue(i);
        // Just access the value. This requres no boxing.
        Object nVal01 = thisComb.GetValue(i);		
}

Combinations、Permutations 和 Variations 类都支持 System.Collections.IEnumerate 接口，因此很容易遍历它们。如果您想重置这些对象，只需调用 Reset() 成员函数。之后，所有组合生成将重新开始。

将要使用的集合作为参数传递给组合对象的构造函数。这意味着在完成使用当前集合后，您不能用新集合重新初始化对象，而必须创建一个全新的 Combinations（或其中其他对象）对象。

有三种可能的构造函数

protected CombinatorialBase(Array arrayObjects, int nKlass );
protected CombinatorialBase(IList listObjects, int nKlass );
protected CombinatorialBase(IEnumerator enumeratorObjects, 
    int nKlass );

如您所见，您可以传递任何支持 IList 或 IEnumerator 接口的集合。或者，您可以传递任何对象数组。这意味着您几乎可以在 .NET 框架中的任何集合上使用这些类。因为组合类本身支持 IEnumerate 接口，所以您实际上可以创建类似“组合的组合”或“变异组合的排列”等结构。然而，我强烈建议您不要这样做（除非组合数量很少的情况下），因为构造函数会遍历它需要操作的所有对象（集合中的对象）。如果您传递另一个组合，此过程可能需要很长时间。

有了以上所有构造函数，我们可以使用如下代码

double[] doubles = new double[10];
for (int j = 0; j < doubles.Length; j++)
    doubles[j] = (double)j;

// Generate the  combinations of 5  numbers from a bunch of 10
Combinations combs = new Combinations(doubles, 5);

或者在使用 ArrayList 时使用如下代码

ArrayList myArrayList = new ArrayList(15);
for (int j = 0; j < 10; j++)
    myArrayList.Add("str"+j.ToString());

// Generate all the permutations of 10 objects.
Permutations perms = new Permutations(myArrayList);

甚至是一些不寻常的结构，比如这里的这个

string myString = "abcdefghij";

// Generate all the possible five char combinations from the 
// letters of this string.
Combination combs = new Combination(myString.GetEnumerator(), 5);

现在给那些会说：“嘿，我们能不能通过生成 5 个元素的变异（大小为 5 的类）来生成所有 5 个元素的排列？”的人一些提示。

这意味着

Permutations combs = new Permutations(myArrayList);

和

Variations combs = new Variations(myArrayList, myArrayList.Count);

实际上做的是同样的事情。

那么，为什么我们需要一个 Permutation 对象，而我们有一个更通用的 Variation 对象呢？事实是，数学上它们是相同的。但是，因为组合和排列的生成算法比变异的算法更容易实现，所以这两个对象是这个库的基础。Variation 对象实际上使用组合和排列来生成所有可能的变异。如果您只需要排列，请始终使用 Permutation 类。

最后要提的一点是：这个库只生成不重复的组合、变异和排列。如果您需要重复，则必须自己实现。我现在没有此类功能的需求，所以可能很快就不会编写它。

结论

有些人可能会问，为什么我没有实现 IEnumerable 接口（就像 String 或 Array 类那样），而是选择了 IEnumerate。 IEnumerable 接口只有一个方法：GetEnumerator()，它返回一个枚举器。每次请求枚举器时，此接口都应返回一个序列的有效枚举器。并且有一点非常重要：如果您之前已经请求过同一个序列的枚举器，那么它必须不能失效，因为它可能仍然在使用中。这在使用当前的组合类实现时是不可能的，而且我看不到轻松修改的方法。所以目前我只提供 IEnumerate。