65.9K
CodeProject 正在变化。 阅读更多。
Home

使用 C# 泛型进行排列、组合和变奏

Adrian Akison
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.97/5 (150投票s)

2008年5月14日

CPOL

20分钟阅读

viewsIcon

821199

downloadIcon

23853

讨论了六种主要的组合集合类型，并提供了计数示例和公式。使用基于 C# 泛类的类集扩展，用于枚举每个元集合。

Combinatorics Sample Program Screenshot

引言

组合数学在计算机科学中有很多应用，可以解决复杂问题。然而，它在库中的代表性不足，因为在商业应用中很少用到组合数学。幸运的是，它的科学已被数学家研究了数个世纪，并且被充分理解和记录。然而，数学家们专注于组合数学问题中的元素数量，而对实际创建这些列表的工作兴趣不大。计算机科学则承担起构建这些庞大数据集的任务。

C++ 标准模板库 (STL) 为我们提供了非常有用的算法 next_permutation，它使用迭代器生成列表的排列。然而，大多数语言，包括 C#，都没有内置的生成这些列表的库。为了弥补这一空白，在不同语言中，人们在排列方面做了大量工作，包括 CodeProject 上的一系列文章。尽管已经做了如此多高质量的工作，我仍然觉得缺少一些额外的功能。特别是，一个能够满足以下所有自我设定的要求的单一解决方案：

  • 使用 C# 泛型实现
  • 能够在开始使用前计算集合的大小
  • 对变奏提供完全支持
  • 面向对象实现（即，不是单一函数接口）
  • 易于使用（例如，与 foreach 高效配合）
  • 在组合类之间提供一致的接口
  • 文档齐全，包括变奏
  • 支持重复和非重复版本

如果您是组合数学新手，那么这些要求中的许多可能没有意义。下面的 背景 部分包含了组合概念的完整概述，包括示例和如何计算输出集的数量。接下来的 使用代码 部分介绍了为每个集合提供的类，并描述了这些类提供的功能；本节包含您需要了解的有关使用随附类的所有信息。然后，算法与性能 部分讨论了考虑过的一些实现选项，并解释了一些主要的设be计决策。最后，示例 部分解释了包含的小示例应用程序，以演示变奏的使用和必要性。

背景

在每个概率课程中都会讲授两个常见的组合概念。它们是排列和组合。还有一个不太为人所知的集合称为变奏，它结合了排列和组合的特征。此外，这三个中的每一种都有涉及在输入或输出中引入重复的变体。这些带有重复的集合在入门课程中也通常被略过。因此，组合集合的完整列表是：

  • 排列
  • 重复排列
  • 组合
  • 重复组合
  • 变奏
  • 重复变奏

排列处理的是一组项目的排序，例如，一副 52 张牌有多少种洗牌方式。组合处理的是一组项目的子集，例如，一副 52 张牌有多少种 5 张牌的扑克牌型。在这两种情况下，牌组或牌型中的每张牌都是唯一的，因此重复不是一个因素。然而，确实会出现输入和/或输出重复的问题。在这些情况下，重复版本为我们构建输出集提供了更多的选择。变奏用于不仅组合提供的子集相关，而且该子集内的排序也相关的情况。以下将逐一介绍。

排列

排列是给定输入集的**所有可能的排序**。每次排序称为一个排列。当输入集中的每个项目都不同时，只有一种方法可以生成排列。但是，当集合中有两个或多个项目相同时，可能存在两种不同的排列集。这些称为**排列**和**重复排列**。

排列（即，无重复）

标准排列仅提供输入集的**每个单个排序**

Permutations of {A B C}:
{A B C}, {A C B}, {B A C}, {B C A}, {C A B}, {C B A}

根据 [2]，排列的数量很容易表示为 P(n) = n!，其中 n 是项目的数量。在上面的示例中，输入集包含 3 个项目，数量为 3! = 6。这意味着排列的数量随 n 指数级增长。即使是较小的 n 也会产生大量的排列；例如，随机洗一副牌的方式是 52!，约等于 8.1E67。

重复排列

重复排列集允许输入集中存在重复的项目，从而减少排列的数量

Permutations with Repetition of the set {A A B}:
{A A B}, {A B A}, {B A A}

重复排列的数量不像标准排列那么多，它会因输入集中重复项目的数量和计数而减少。对于每组 m 个相同的项目，总计数会减少 m!。在上面的示例中，输入集包含 3 个项目，其中一个子集有 2 个相同的项目，数量为 3! / 2! = 6 / 2 = 3。这个计数的概念比公式更容易理解，因为公式需要每个重复集的大小 ri 的乘积。总大小为 Pr(n) = n! / Π(ri!)（其中 Π 是乘积运算符）。所有排序和计算都通过 Permutation.Count 属性处理。

随本文提供的代码库将根据输入集确定使用哪种类型的排列。或者，可以提供一个类型来确定使用哪种排列类型。

组合

组合是从给定输入集中选取**给定大小的子集**。集合的大小称为上指标 (n)，子集的大小称为下指标 (k)。在计算组合的数量时，术语通常是“n 选 k”，称为二项式系数 [3]。与排列不同，组合在输出集中没有顺序。与排列一样，它们也有两种生成方法，基于输出项目的重复。它们被称为**组合**和**重复组合**。

组合（即，无重复）

组合可以想象成将一组 n 个多米诺骨牌放入帽子中，然后取出 k 个。每张牌只能选择一次，它们从帽子中取出的顺序无关紧要。

类似地，可以将 (n = 100) 张拼字游戏牌放入袋子中，第一位玩家将选择 (k = 7) 张牌。然而，袋子里有 9 张 A，选择 {A A A A A A A} 是一个有效但不太可能出现的抽奖。由于袋子里只有 6 张 N，因此不可能抽到 7 张 N。因此，对于组合，牌的值被忽略，这与排列不同。

Combinations of {A B C D} choose 2:
{A B}, {A C}, {A D}, {B C}, {B D}, {C D}

这个特定示例中的输出数量**是**二项式系数。它可以计算为 n! / ( k! * (n - k)! ) [4]。上面的拼字游戏示例将给出 100! / (7! * 93!) = 16,007,560,800。请注意，100! 的答案比这里大得多，因为它的绝大部分幅度被 93! 消除了。

重复组合

重复组合是检查一个项目集，并选择一个子集，同时允许重复。例如，从上面的拼字游戏袋中选择一张牌，写下字母，然后将字母放回袋中。执行此操作 7 次以生成一个样本。在这种情况下，您可以“抽到”7 张 N，只是抽到 7 张 A 的概率较低。

因此，重复组合是组合的超集，如下例所示：

Combinations with Repetition of {A B C D} choose 2:
{A A}, {A B}, {A C}, {A D}, {B B}, {B C}, {B D}, {C C}, {C D}, {D D}

组合用于大量的游戏类型问题。例如，一副 (n = 52) 张牌，从中抽取 (k = 5) 张牌。使用所有组合的集合可以为有关扑克牌型的统计问题提供一种暴力破解机制。

变奏

变奏结合了组合和排列的特征，它们是一组用于构成子集的**所有有序组合**。与组合一样，集合的大小称为上指标 (n)，子集的大小称为下指标 (k)。并且，变奏的生成可以基于输出项目的重复。这些称为**变奏**和**重复变奏**。

变奏（即，无重复）

变奏是组合的排列。也就是说，n 个项目选择 k 个的集合的变奏，是大小为 k 的**有序子集**。例如：

Variations of {A B C} choose 2:
{A B}, {A C}, {B A}, {B C}, {C A}, {C B}

这个特定示例中的输出数量类似于 n 选 k 的组合数除以 k 的排列数。它可以计算为 V(n, k) = C(n, k) * P(k) = (n! / ( k! * (n - k)! )) * k! = n! / (n - k)!。随附的示例项目使用变奏来选择数字替换简单密码学文字问题中的字母。

重复变奏

重复变奏扩展了变奏集，并允许重用项目。由于每个项目都可以重用，因此这允许变奏包含输出中的所有项目都来自输入中的单个项目。例如：

Variations with Repetition of {A B C} choose 2:
{A A}, {A B}, {A C}, {B A}, {B B}, {B C}, {C A}, {C B}, {C C}

变奏的输出集大小更容易计算，因为不涉及阶乘。p 个位置中的每个位置都可以从输入集中的 n 个位置中的任何一个填充。第一个项目是 n 个项目中的一个，第二个也是 n 个中的一个，第 p 个也是 n 个中的一个。这给了我们 Vr(n, k) = nk 个 n 个项目选择 k 的总变奏数。

Using the Code

枚举集合

代码库中有三个类入口点：Permutations、Combinations 和 Variations。它们都是基于集合中项目类型 T 的泛型类。它们都基于输入集生成集合的集合，使每个类都成为一个元集合。为了方便使用，这些类实现了 IEnumerable<T>，它返回一个 IList<T>。但是，这种泛型代码的设计旨在使每个类的使用变得容易。例如，使用 Permutations：

char[] inputSet = {'A', 'B', 'C'};
  
Permutations<char> permutations = new Permutations<char>(inputSet);
foreach(IList<char> p in permutations) {
  Console.WriteLine(String.Format("{{{0} {1} {2}}}", p[0], p[1], p[2]));
}

将生成：

{A B C}
{A C B}
{B A C}
{B C A}
{C A B}
{C B A}

使用 Combinations 和 Variations 类似，但必须同时指定下指标。（上指标从输入集的大小推导出来。）例如：

char[] inputSet = { 'A', 'B', 'C', 'D' };
  
Combinations<char> combinations = new Combinations<char>(inputSet, 3);
string cformat = "Combinations of {{A B C D}} choose 3: size = {0}";
Console.WriteLine(String.Format(cformat, combinations.Count));
foreach(IList<char> c in combinations) {
  Console.WriteLine(String.Format("{{{0} {1} {2}}}", c[0], c[1], c[2]));
}

Variations<char> variations= new Variations<char>(inputSet, 2);
string vformat = "Variations of {{A B C D}} choose 2: size = {0}";
Console.WriteLine(String.Format(vformat, variations.Count));
foreach(IList<char> v in variations) {
  Console.WriteLine(String.Format("{{{0} {1}}}", v[0], v[1]));
}

将生成：

Combinations of {A B C D} choose 3: size = 4
{A B C}
{A B D}
{A C D}
{B C D}
Variations of {A B C D} choose 2: size = 12
{A B}
{A C}
{A D}
{B A}
{C A}
{D A}
{B C}
{B D}
{C B}
{D B}
{C D}
{D C}

带重复和不带重复

默认情况下，Permutations、Combinations 和 Variations 将生成标准或无重复集。每个类都有一个重载的构造函数，该构造函数接受一个 GenerateOption，它可以是 GenerateOption.WithoutRepetition（默认值）或 GenerateOption.WithRepetition。例如，生成带重复和不带重复的排列集：

char[] inputSet = { 'A', 'A', 'C' };
  
Permutations<char> P1 = new Permutations<char>(inputSet, 
      GenerateOption.WithoutRepetition);
string format1 = "Permutations of {{A A C}} without repetition; size = {0}";
Console.WriteLine(String.Format(format1, P1.Count));
foreach(IList<char> p in P1) {
  Console.WriteLine(String.Format("{{{0} {1} {2}}}", p[0], p[1], p[2]));
}

Permutations<char> P2 = new Permutations<char>(inputSet, 
      GenerateOption.WithRepetition);
string format2 = "Permutations of {{A A C}} with Repetition; size = {0}";
Console.WriteLine(String.Format(format2, P2.Count));
foreach(IList<char> p in P2) {
  Console.WriteLine(String.Format("{{{0} {1} {2}}}", p[0], p[1], p[2]));
}

将生成：

Permutations of {A A C} without Repetition; size = 3
{A A C}
{A C A}
{C A A}
Permutations of {A A C} with Repetition; size = 6
{A A C}
{A C A}
{A A C}
{A C A}
{C A A}
{C A A}

请注意，Permutations 的输入集必须包含重复项才能看到输出的差异。Combinations 和 Variations 将生成额外的集合，而不管传入值的相似性如何。

计数和其他属性

虽然这些类的目的不是计算二项式系数，但每个类都有一个 Count 属性。此属性将计算返回的集合的实际数量，而无需迭代它们。这是通过应用上面通用讨论中的公式来完成的，并将值作为 long 返回。最后，计数是在没有内部溢出的情况下完成的，这一点很重要，因为 21! 会溢出 long。

构造函数参数也可用；上指标和下指标分别通过 UpperIndex 和 LowerIndex 访问。生成器选项可通过 Type 属性访问。例如：

char[] alphanumeric = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".ToCharArray();
Combinations<char> C = new Combinations<char>(alphanumeric, 10);
Console.WriteLine(String.Format("{0} choose {1} = {2}", C.UpperIndex, 
      C.LowerIndex, C.Count));

将生成：

36 choose 10 = 254186856

最后，这些通用功能通过这些类都实现的 IMetaCollection 接口得到了形式化。

算法与性能

至此，我们已经涵盖了理解和使用这些类所需的一切。讨论的其余部分描述了一些实现中使用的背景和决策过程。

排列、组合和变奏的数量都会呈指数级增长。因此，在非平凡的项集上进行元集合枚举将很快超出任何可用计算时间。例如，一个能在 1 秒内枚举 10 个项目的排列的系统，将需要 1000 多年才能枚举 20 个项目的排列。由于即使是最佳算法的性能也会下降，所以几乎任何算法都可以。然而，如果不评估选项并为工作选择最佳算法，任何开发人员都无法自豪。即使这样，也可能只会将 1000 年的运行时间缩短 50 年。

算法选择

计算排列的能力是所有组合类的核心。已经开发了几种计算排列的算法，其中三种被评估用于此实现，即递归算法、字典序算法和 Heap 算法 [1]。字典序算法 [3] 非常适合 IEnumerable 接口，因为它使用相同的 GetNext() 样式，并且只需要很少的适应。递归和 Heap 算法在生成整数排列方面更有效，但需要通过转换为迭代算法或使用 C# 延续来适应 IEnumerable 接口。

第一次尝试是采用更有效的基于 Heap 的算法并将其展开为迭代算法，然后使其符合 IEnumerable 接口的每次调用返回一个结果的行为。两种 Heap 算法都存储了相当多的状态信息，并且不容易展开。完成后，它们都从比字典序算法快大约两倍变成了比其慢大约两倍。

第二次尝试是使用 .NET 2.0 中添加到 C# 的延续功能。此功能提供了 yield return 语法，用于快速创建枚举器。它还可以处理递归枚举器，只需稍加努力即可。好消息是这种机制有效，但性能比展开递归算法还要差 4 倍。

因此，字典序算法被选为本次实现最佳算法。

比较效率

下一个问题涉及比较的性能。所有测试的算法都必须进行更改以适应非整数数据。字典序算法需要比较对象以确定它们的排序顺序，以便能够创建唯一的字典序。解决此问题的标准方法涉及 IComparable 或 IComparer 接口来确定顺序。由于这是一个泛型集合，因此将整数比较改编为提供比较的 IComparer 是相对直接的。不幸的是，这种比较被调用了很多次，任何低效都会被放大。由于这是泛型类型比较，CLR 的优化效率远不如值类型。

使用直接比较对象进行排列的另一个问题是，排列将始终是重复的，而不是非重复的。也就是说，您无法创建 {A A B} 的非重复排列。与上述性能问题一起，还需要另一种解决方案。

最终的解决方案是有一个并行的整数数组，在上面执行比较。两个数组将并行地交换项目，从而产生正确的输出。性能提高了几个百分点，接近算法最初的仅整数解决方案。重复和非重复集合的解决方案是通过在并行数组中具有不同的整数分配来完成的。对于重复，{A A B} 的分配是 {1 2 3}，对于非重复，分配是 {1 1 2}。IComparer 用于对列表进行排序，然后在选择重复模式时再次用于检查相邻的重复项，但在此过程中不使用 GetNext() 调用。

组合和变奏的效率

大多数关于算法的研究似乎都集中在排列上，而对组合和变奏的研究较少。因此，组合和变奏的实现使用内部排列来计算它们的集合。例如，Combinations 类使用一个 Permutations<bool> 类来指示要包含的位置。这个底层类的排列指示了组合要选择的子集。变奏也使用类似的机制，除了重复变奏。

因此，在使排列高效工作的成果被组合和变奏继承。组合和变奏实现中的其他性能改进未被寻求。

计数

首先，这些类并非设计用于高效计算二项式系数表。然而，它们需要提供当前枚举的集合的计数。如上所述，这些值可能非常大，并且很容易溢出 64 位整数。但是，计数公式中的除数将值带回可管理的级别。因此，为了正确计算这些集合的数量，需要执行某种类型的长整数计算。

这些计数的输出显然总是整数，因此公式分母的素因数总能在分子素因数中找到。与其执行大整数计算，不如计算分子素因数列表和分母素因数列表。然后，从分子列表中删除分母列表，并返回剩余分子的乘积。没有尝试比较此过程的效率，请参阅上面的段落。

如果您查看代码，您会发现一个 SmallPrimeUtility 类，用于上述算法。我对该类适用于其他任何用途的适用性不作保证，它是一个非常基础的类，没有任何优雅之处。它是类的 Hyundai Excel，它能带您到达目的地，但仅此而已。

想看真正的性能

此处创建的类旨在穷尽枚举大量的集合。对于大多数非平凡的集合，枚举所需的时间超过了所有可用计算能力。因此，有时有必要通过暴力破解来解决问题，但您无法为大 N 做到这一点，这使得计算机科学变得有趣。对于小问题，这套类是适用的；对于大问题，这套类可以帮助快速验证其他更有趣的算法。对于大问题，您需要一个敏锐的头脑，而不是一台笨重的计算机。

对于更复杂的排列或组合相关问题，总解空间 S 的增长速度太快，以至于无法评估每个选项。这些类旨在枚举 S 中的每个排列；然而，许多问题呈现出较小的可行搜索空间 F。 [5]。例如，在以下数字替换问题中：

  F O U R
+ F I V E
---------
  N I N E

有 8 个变量 {F O U R I V E N} 需要从 10 位数字 {0 1 2 3 4 5 6 7 8 9} 中选择。这意味着解空间 S 中有 10 选 8 的变奏可能性，即 10! / 2! = 1,814,800 种变奏。然而，可以做出一些观察；例如，第四列提供了 R + E = E，这意味着 R = 0。这已将问题简化为从 9 位数字中选择 7 个未知变量，或 9! / 2! = 181,480 种变奏。此外，第一列暗示 F <= 4，因为我们不能允许此列溢出。这消除了需要测试的剩余变奏的 5/9，留下 80,640 种变奏待测试。还存在其他简化，并将进一步减小空间。

重点是，我们对问题的具体情况了解越多，就越有可能减小可行搜索空间的大小，也越有可能在合理的时间内解决问题。

示例

上面的 FOUR + FIVE 问题只是近乎无限的数字替换字母问题中的一个。这可以用来证明 THREE + SEVEN = EIGHT，甚至 WRONG + WRONG = RIGHT。使用附带的示例，您可以输入操作数和总和，并让程序搜索任何和所有解决方案。该程序使用 Variations 类来穷举搜索每种可能的变奏，并检查变奏是否满足方程。

Combinatorics Sample Program Screenshot

用户界面

要计算一个问题，只需在操作数字段中输入操作数，例如“FOUR”和“FIVE”，然后在总数字段中输入总和，例如“NINE”。问题框架将自动更新以呈现加法问题。请确保输入的独特字符不超过 10 个，因为对此输入不进行任何验证。输入超过 10 个将确保找不到解决方案。还有更多确保不存在解决方案的方法，例如 A + BC = DEFGH。界面将愉快地接受这些输入，然后返回未找到解决方案。

输入问题后，单击“Solve”将枚举输入中每个字符的 1 到 10 位数字的所有可能变奏。状态栏将显示将要检查的总变奏数；这将根据输入中唯一字符的数量而变化。从 A + A = B 的 90 种变奏的低值，到 10 个字符（如 ABCDE + ABCDE = FGHIJ）的 3,628,800 种变奏的高值。进度条将指示整体进度，对于这些问题中的任何一个，应该只需要几秒钟。解决方案框架将显示找到的总数和最近找到的解决方案，因为程序正在进行中。

找到所有解决方案后，选择解决方案框架中的下拉列表以浏览找到的所有解决方案。

代码

Facet.Combinatorics 命名空间包含在示例的 Combinatorics 子目录中。它包含了支持 Permutations、Combinations 和 Variations 所需的所有代码。除了标准的 .NET 2.0 System 引用外，它没有任何依赖项。此目录可以移入其他解决方案以利用这些类，而无需创建单独的库。

窗体代码是纯粹的香草代码，不是生产就绪的用户界面，可以安全地忽略。它包含了所有用户界面元素，并将问题求解委托给 TextSumProblem 类，该类封装了此特定问题。

示例的核心在于 TextSumProblem，它创建了问题的每种可能的变奏。解决方案的核心是生成所有可能的整数变奏，这些变奏可以作为问题的字母候选。在示例中，Solve() 方法的逻辑类似于：

int[] ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
Variations<int> variations = new Variations<int>(ints, 8);
foreach(IList<int> variation in variations) {
  if(Satisfies(variation) == true) {
      // Huzzah, found a solution...
  }
}

最后，TextSumProblem 具有一对事件，当尝试了一个候选解决方案时以及找到一个解决方案时发出信号。窗体订阅这些事件以提供问题进度的实时反馈。

可以创建任意数量的有趣示例来“证明”各种矛盾。大多数示例会有多个解决方案（ID + EGO = SELF 有 1200 个解决方案，尽管这有点取巧），如果您找到一个具有唯一解决方案的好示例，请告诉我，我从未找到过。

参考文献

  1. A. Bogomolny，“Counting And Listing All Permutations”，Interactive Mathematics Miscellany and Puzzles (2008-04-28)
  2. J. Claeys，“Counting Problems”，MATH-abundance，(2008-04-28)
  3. E. W. Dijkstra，A Discipline of Programming，Prentice-Hall，1997
  4. R. L. Graham, D. E. Knuth, O. Patashnik，Concrete Mathematics，Addison-Wesley，1994
  5. Z. Michalewicz, D. B. Fogel，How to Solve It: Modern Heuristics，Springer-Verlag，2000

历史

  • 2008-05-24
    • 修复了文章中的拼写错误。
    • 修改了排列迭代器的当前方法，使其返回列表的副本。
  • 2008-05-14
    • 原始文章。
© . All rights reserved.