测试运行

使用 F# 的排列与组合

James McCaffrey

下载示例代码

理解排列与组合是进行软件测试所需的一项基本技能。在本月的“测试运行”专栏中，我将向您展示如何使用以新 F# 语言编写的代码来处理排列与组合。

数学组合是指从包含 n 项的集合中选择 k 项作为子集，不考虑其中的顺序。例如，如果 n = 5 且 k = 2，需要从五项中选择二项，则所有可能的组合为：

{0,1}, {0,2}, {0,3}, {0,4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}

请注意，我没有列出组合 {1,0}，这是因为它与 {0,1} 被视为相同的组合。另外，我使用的是一种称为字典编辑顺序的顺序列出这 10 个一次性五选二的组合。根据这种顺序，每个组合元素中的所有值以递增顺序列出。

数学排列是指对 n 项进行所有可能的排列。例如，如果 n = 4，以字典编辑顺序列出的所有可能的排列为：

{0,1,2,3}, {0,1,3,2}, {0,2,1,3}, {0,2,3,1}, {0,3,1,2}, {0,3,2,1}, {1,0,2,3}, {1,0,3,2}, {1,2,0,3}, {1,2,3,0}, {1,3,0,2}, {1,3,2,0}, {2,0,1,3}, {2,0,3,1}, {2,1,0,3}, {2,1,3,0}, {2,3,0,1}, {2,3,1,0}, {3,0,1,2}, {3,0,2,1}, {3,1,0,2}, {3,1,2,0}, {3,2,0,1}, {3,2,1,0}

在处理排列与组合时，有两个重要的函数：Choose(n,k) 和 Factorial(n)。您可能熟悉 Factorial(n) 函数，该函数通常缩写为 n!。Factorial(n) 函数返回 n 阶排列的元素总数。例如：

4! = 4 * 3 * 2 * 1 = 24.

Choose(n,k) 函数返回 n 选 k 组合的总数。

Choose(n,k) = n! / (k! * (n-k)!)

例如，

Choose(5,2) = 5! / (2! * (5-2)!) = 5! / (2! * 3!) = 120 / 12 = 10.

排列与组合是“组合数学”（或简称“组合学”）的研究范畴。

为了您了解我在本月专栏中要谈的问题，最好先看一下图 1 所示的屏幕截图。我使用了 Windows PowerShell 来承载我的 F# 演示应用程序，但也可以只简单地使用命令 Shell。我修改了 Windows PowerShell 启动脚本，以便能自动导航到我的 CombinatoricsDemo.exe 程序所在的位置。

图 1 使用 F# 的排列与组合

在后台，该演示程序会引用并调用一个名称为 CombinatoricsLib 的 F# 代码库。演示开始时列出一次性五选三的所有数学组合。接下来，它使用一个帮助程序方法将最后一个组合元素 {2,3,4} 应用于字符串数组 {ant, bat, cow, dog, elk}，得出 {cow, dog, elk}，也就是原始集合中索引值分别为 2、3 和 4 的三个字符串。

演示程序继续运行，开始计算并显示 Choose(200,10) 的值，即从包含 200 项的集合中选择 10 项（不考虑顺序）的组合方式总数。

接着，演示代码计算并显示 Factorial(52) 的值，也就是一副标准扑克牌（52 张）的排列方式总数。请注意，这里得出的结果是一个极其庞大的数字。F# 可以处理任意大的整数值，这一点我稍后会讲到。

最后，演示程序列出了阶 n = 3 的所有数学排列。

接下来，我将详细讲述 CombinatoricsLib 模块中的 F# 代码，以及图 1 中运行的 F# 演示程序的代码。在此过程中，我会比较 F# 与其他语言（如 Visual Basic 和 C#）在处理排列与组合方面的使用异同。

本专栏假设您的 .NET 语言（如 C#）水平为入门级到中级水平，且对 F# 有最基本的了解。不过，即使您从未接触过 F#，应当也能理解我讲的内容。

F# CombinatoricsLib 库

在创建组合库时，我使用了 Visual Studio 2010 的 Beta 2 版本，该版本内置了 F# 语言及工具。我想此处展示的 F# 代码应该也能够用于 Visual Studio 2010 的发行版本，不需要太大的更改。如果您使用的是较早的 Visual Studio 版本，可在 Microsoft F# 开发人员中心 (msdn.microsoft.com/fsharp) 查找 F# 工具。除 F# 语言外，Visual Studio 2010 还附带了 Microsoft .NET Framework 4，我的库会用到它。

我通过以下方法创建库：启动 Visual Studio 2010，然后选择“文件”|“新建”|“项目”。在新建项目对话框中，选择 F# 库模板，然后将库命名为 CombinatoricsLib。CombinatoricsLib 的整体结构如图 2 所示。

图 2 F# CombinatoricsLib 结构

module Module1

open System
open System.Numerics // BigInteger class

type Combination(n : int, k : int, a : int[]) = 
  // primary constructor code
  new(n : int, k : int) =
    ...
  member this.IsLast() : bool =
    ... 
  member this.Successor() : Combination =
    ... 
  member this.ApplyTo(a : string[]) : string[] =
    ...
  override this.ToString() : string =
    ... 
  static member Choose(n : int, k : int) : BigInteger =
    ...
  static member Factorial(n : int) : BigInteger =
    ...  
// end type Combination

type Permutation(n : int, a : int[]) =
  // primary constructor code
  new(n : int) =
    ...
  override this.ToString() : string =
    ...
  member this.Successor() : Permutation =
    ... 
  member this.ApplyTo(a : string[]) : string[] =
    ...
  member this.IsLast() : bool =
// end type Permutation

该库的代码开始部分为 Visual Studio 生成的代码，该代码将库命名为 Module1。我使用了这个非常没有特点的默认名称，而并未将其更名为更具描述性的其他名称，这样做是为了在本文后面部分使访问库的语法更突出。

接着，我将两条 F# open 语句添加到顶级的 System 命名空间及新的 System.Numerics 命名空间，这样我不必完全限定类名即可访问这些命名空间中的类。System.Numerics 命名空间是 .NET Framework 4 的一部分，它包含的 BigInteger 定义可让我处理任意大的整数值。

用 F# 定义一个“类型”与用 C# 定义概念上类似的“类”是不同的。类型定义中有一个签名，此签名包含主类型构造函数的输入参数。

type Combination(n : int, k : int, a : int[]) =

此签名的含义是“我在定义一个名称为 Combination 的类型，该类型的主构造函数接受整数类型的参数 n（总项数）、k（子集大小）以及一个整数数组 a（用于指定各个组合值，例如 {0,1,4}）。”

F# 类型可以有可选的辅助构造函数，例如图 2 中所列的辅助构造函数：

new(n : int, k : int) =

请注意，相对于主类型构造函数，辅助构造函数使用显式的 new 关键字。这个辅助构造函数只接受 n 和 k 的值。而对于其他编程语言（如 C#），您可能需要定义与主构造函数一样较为简单的辅助构造函数（即在负责接受参数的构造函数前面执行定义）。但在 F# 中可以看到，对于拥有多个构造函数的类型，通常在创建类型时最好是将主构造函数作为参数最多的构造函数。我的 Combination 类型的结构中还紧跟着三个成员函数：

member this.IsLast() : bool =
  ... 
member this.Successor() : Combination =
  ... 
member this.ApplyTo(a : string[]) : string[] =
  ...

其中的 this 关键字将公共可见的成员方法绑定到外部调用代码。如果关联的 Combination 对象是以字典编辑顺序列出的最后一个元素（例如当 n = 5 且 k = 3 时的 {2,3,4}，如图 1 所示），IsLast 函数将返回 true。

Successor 函数返回以字典编辑顺序列出的当前 Combination 元素的下一个元素。

ApplyTo 函数接受字符串数组，返回对应于当前 Combination 元素的字符串数组。

下一个类型成员函数提供了 Combination 元素的显示方式：

override this.ToString() : string =

我使用 override 关键字将我的自定义函数 ToString 与基类方法 ToString 区别开来。由于 F# 是一种 .NET 语言，因此所有对象都继承自一个具有 ToString 方法的通用基类 Object。请注意，尽管被覆盖的 ToString 函数有一个公共作用域，我也未使用 member 关键字。

Combination 类型中的最后两个成员函数定义的是 Choose 和 Factorial 函数：

static member Choose(n : int, k : int) : BigInteger =  ...
static member Factorial(n : int) : BigInteger =  ...

两个函数都是静态函数，这表示这两个函数与 Combination 类型的上下文相关联并直接在该上下文中调用，而不是与 Combination 类型的具体实例相关联或在其中调用。两个函数都返回 BigInteger 类型，这种类型定义在 System.Numerics 命名空间中，而默认情况下该命名空间对于 F# 代码而言是直接可见的。

除 Combination 类型之外，我还定义了一个 Permutation 类型，如图 2 所示。

F# 组合库实现

现在，我们回顾一下 CombinatoricsLib 库的实现细节。Combination 主构造函数的开始部分为：

type Combination(n : int, k : int, a : int[]) = 
  do if n < 0 || k < 0 then failwith 
    "Negative argument in Combination ctor"
  do if n < k then failwith 
    "Subset size k is larger than n in Combination"

有趣的是，为了在主构造函数中执行输入参数的验证，应该使用 do 关键字，该关键字表示一项“操作”，而不是 F# 之类的函数式语言所通常默认为的“值”。failwith 关键字用于抛出异常，该异常可由调用代码捕获到。

接下来设置 Combination 类型的私有成员：

let n : int = n // private
let k : int = k
let data = 
  [| for i = 0 to a.Length-1 do yield a.[i] |]

let 关键字将值绑定到私有成员。注意，我可以使用小写的 n 和 k 同时作为输入参数和私有字段。这看起来有点不方便，因此在大多数情况下，我对参数和私有成员二者中的一种采用大写表示法。

将输入参数数组 a 的值复制到类型字段数据时使用标准的 F# 风格。[| .. |] 分隔符表示可变数组。Combination 辅助构造函数将创建一个初始的 Combination 对象，其定义为：

new(n : int, k : int) = 
  do if n < 0 || k < 0 then failwith 
    "Negative argument in Combination ctor"
  do if n < k then failwith 
    "Subset size k is larger than n in Combination"
  let starters = [| for i in 0..k-1 -> i |] 
  new Combination(n,k,starters)

在 F# 中，辅助构造函数必须调用主构造函数。因此，我定义了一个名为 starters 的整数数组且其值为 0 到 k-1，并将该数组随 n 和 k 一起传递给主构造函数。F# 的这种机制就是建议将主构造函数定义为参数最多的构造函数的原因。

IsLast 成员函数的定义如下：

member this.IsLast() : bool =
  if data.[0] = n-k then true
  else false

注意在图 1 所示的全部组合中，只有最后一个元素在数组的第一个位置处的值为 n-k。F# 并不像大多数语言那样使用显式的 return 关键字，而是使用隐式的返回方式，为函数中的最后一个值，在本例中为 true 或 false。= 标记用于检查 F# 中的相等情况，并不是赋值运算符。Combination.Successor 函数为：

member this.Successor() : Combination =
  // copy input to temp array
  let temp = [| for i in 0..k-1 -> data.[i] |] 
  // find "x" - right-most index to change 
  let mutable x = k-1 
  while x > 0 && temp.[x] = n - k + x do 
    x <- x - 1
  temp.[x] <- temp.[x] + 1 // increment value at x
  // increment all values to the right of x
  for j = x to k-2 do 
    temp.[j+1] <- temp.[j] + 1
  // use primary ctor
  let result = new Combination(n, k, temp) 
  result

首先，我将当前 Combination 对象上下文的值复制到名为 temp 的可变数组。接下来，我定义一个名为 x 的索引变量，并将其置于 temp 数组的末尾。我必须使用 mutable 关键字，这样才能递减此索引变量，因为默认情况下 F# 中的大多数变量是不可变的。我使用了 <- 赋值运算符。

每次定位到当前 Combination 对象的键索引后，我便递增一次该值及键索引右边的所有值。然后，我将 temp 数组（现在其值为 Combination 后继元素的值）传递到主构造函数，并返回新创建的对象。

请注意，我到达最后一个 Combination 元素时并未返回 null（在 F# 中，这种做法被认为是不好的风格）。我在本文中展示的代码的风格不太符合 F# 风格。F# 专家可能会使用递归方法，但由于我这里认为读者是 F# 的初学者，因此我的初衷是尽量使 F# 代码为读者所熟悉。

另一种编写 Successor 函数的做法是实现 .NET IEnumerable 接口。

通过 ApplyTo 函数可将一个组合元素映射到一个字符串值集合：

member this.ApplyTo(a : string[]) : string[] =
  if a.Length <> n then failwith 
    "Invalid array size in ApplyTo()"
  // array of int
  let result = Array.zeroCreate k
  for i = 0 to k-1 do
    // bind to array of string
    result.[i] <- a.[data.[i]]
  result

在成员函数中执行输入参数的检查时，我不需要像在类型构造函数中那样要使用 do 关键字。静态方法 Array.zeroCreate 将创建一个整数数组，且全部初始化为 0 值。ApplyTo 函数比较简单，因为子集大小为 k (0..k-1) 的数学组合中的值范围与大小为 k 的 .NET 数组的索引是完全相同的。

被覆盖的 ToString 成员函数仅用于构建一个由上下文对象的值组成的字符串：

override this.ToString() : string =
  let mutable s : string = "^ "
  for i in 0..k-1 do
    s <- s + data.[i].ToString() + " "
  s <- s + "^"
  s

我决定用 ^（脱字号，以字母 c 开头）字符来分隔 Combination 元素，而用 %（百分号，以 p 开头）字符分隔 Permutation 元素，从而帮我识别某个数字字符串代表的是 Combination 对象还是 Permutation 对象。

静态函数 Choose 的代码如图 3 所示。 

图 3 Choose 函数

static member Choose(n : int, k : int) : BigInteger =
  if n < 0 || k < 0 then failwith 
    "Negative argument in Choose()"
  if n < k then failwith 
    "Subset size k is larger than n in Choose()"
  let (delta, iMax) =
    if k < n-k then
      (n-k, k)
    else
      (k, n-k)
  let mutable answer : BigInteger = 
    bigint delta + bigint 1 
  for i = 2 to iMax do
    answer <- (answer * (bigint delta + bigint i )) 
      / bigint i
  answer

我没有使用本文前面介绍的定义来计算 Choose，而是使用了两次优化。首先，我使用一个原理 Choose(n, k) = Choose(n, n-k)。例如，Choose(9,6) = Choose(9,3)。其次，我不计算三个单独的阶乘（每个阶乘都会很大），而是计算一组部分乘积。为了将整数值显式转换为 BigInteger 类型，我使用了内置的 F# bigint 函数。

Permutation 类型的实现与 Combination 类型的实现非常相似。您可以从 Microsoft 代码库网站 (code.msdn.microsoft.com) 获取 CombinationLib 库的完整源代码。

使用 CombinatoricsLib

本节中，我将讲述如何调用 CombinatoricsLib 库中的函数来得到图 1 的屏幕截图所示的运行结果。首先启动 Visual Studio 2010，并新建一个名为 CombinatoricsDemo 的 F# 应用程序项目。完整程序如图 4 所示。

图 4 使用 CobinatoricsLib

open System
open Module1 // the Combinatorics Lib

try

  printfn "\nBegin combinations and permutations with F# demo\n"
  printfn "All combinations of 5 items 3 at a time in lexicographical order are: \n"
  let mutable c = new Combination(5,3)
  printfn "%A" c // print initial combination

  // objects cannot be null in F# so use an explicit method
  while c.IsLast() = false do 
    c <- c.Successor()
    printfn "%A" c
   
  printf "\nThe last combination applied to array [| \"ant\"; \"bat\"; \"cow\"; \"dog\"; \"elk\" |] is: \n"
  let animals = [| "ant"; "bat"; "cow"; "dog"; "elk" |]
  //let result =  c.ApplyTo(animals)
  let result = animals |> c.ApplyTo
  printfn "%A" result

  printfn "\nThe number of ways to Choose 200 items 10 at a time = Choose(200,10) ="
  let Choose_200_10 = Combination.Choose(200,10).ToString("000,000")
  printfn "%s" Choose_200_10

  printfn "\nThe number of ways to arrange 52 cards = 52! = "
  let Factorial_52 = Combination.Factorial(52).ToString("000,000")
  printfn "%s" Factorial_52

  printfn "\nAll permutations of 3 items in lexicographical order are: \n"
  let mutable p = new Permutation(3)
  printfn "%A" p // print initial permutation
  while p.IsLast() = false do
    p <- p.Successor() 
    printfn "%A" p
      
  printfn "\nEnd demo\n"
  Console.ReadLine() |> ignore

with
  | Failure(errorMsg) -> printfn "Fatal error: %s" errorMsg

// end program

编写代码之前，我在 Visual Studio 的“解决方案资源管理器”窗口中右键单击该项目名称，然后从上下文菜单中选择“添加引用”选项。然后，选择“浏览”选项卡，并导航到 CombinatoricsLib.dll 程序集。

在演示程序代码的开头，我将 open 语句添加到 System 和 Module1 程序集。请回顾一下前文，CombinatorcsLib 的模块名称为 Module1。我将所有程序语句封装在一个 try/with 块中，以便捕获并处理异常。我使用辅助构造函数实例化 Combination 对象，从而得到初始的五选三数学组合对象 c：{0,1,2}。我使用的是简明的 F# %A 格式说明符，该符号会指示 F# 判定如何输出 Combination 对象。我也可以使用 %s 字符串格式。

接着，我使用 F# while..do 循环来循环访问并显示全部 10 个 Combination(5,3) 元素。此时，Combination 对象 c 成为最后一个元素，因此我调用 ApplyTo 函数将该组合映射到一个字符串数组。

请注意，我是在 Combination 类型的上下文中调用 Choose 和 Factorial 函数的，而不是在 c Combination 对象的上下文中进行调用。在以类似方式调用 Permutation 类型代码后，演示程序使用 Console.ReadLine 方法（在该方法中，我将返回值传送给内置的 ignore 对象）暂停用户输入，从而结束程序。我使用了 with 块来处理可能发生的异常，这里只是简单地显示异常错误消息。

除了刚才演示的在 F# 程序中调用 F# 库，您还可以在任何兼容 .NET 的语言中调用 F# 库。此外，在 Visual Studio 中还可以使用很方便的 F# 交互式窗口进行临时调用，如图 5 所示。

图 5 交互使用 F# 库

在屏幕底部的 F# 交互式窗口中，我通过键入以下内容添加了对 CombinatoricsLib 程序集的引用：

#r @"C:\(path)\CombinatoricsLib.dll";;

在本例中，#r 表示添加引用，;; 表示终止交互式 F# 语句。现在我能够以交互方式调用库中的函数了。太巧妙了！

 我认为，使用 F# 有几项优缺点。就缺点而言，我发现学习 F# 的过程比我预期的要难得多。以函数式风格编程对我而言也是一个巨大的风格转变。另外，较之其他语言更大的不同在于，F# 可以用多种方式来完成某个特定任务的编码工作，因此我感觉不容易确定自己写的 F# 代码是否就是最佳的编码方式。

但至少就我而言，我觉得学习 F# 的收获大于付出，绝对值得。在与经验丰富的 F# 编码人员交流时，大部分人都告诉我：在多数情况下，尽管某个任务实际会有多种编码方法，但具体采用哪种方法更多的是一种个人喜好问题，而不在于技术效率。另外，通过攻克 F# 语法和编码风格（例如克服定势思维），我更深入地理解了过程性语言（如 C#）的编码。

James McCaffrey 博士供职于 Volt Information Sciences, Inc.，他在公司负责管理对华盛顿州雷蒙德市沃什湾 Microsoft 总部园区的软件工程师进行的技术培训。他参与过多项 Microsoft 产品的研发工作，其中包括 Internet Explorer 和 MSN Search。McCaffrey 博士是《.NET 软件测试自动化之道》（Apress，2006）的作者。可通过 jammc@microsoft.com 与他联系。

衷心感谢以下技术专家，感谢他们审阅了本文：Brian McNamara、Paul Newson 和 Matthew Podwysocki