《使用 F# 的排列与组合》学习笔记

在做projectEuler 23题的时候需要时候排列组合的知识。



  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