# 使用 F# 的排列与组合

### James McCaffrey

`{0,1}, {0,2}, {0,3}, {0,4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,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}`

`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.
``````

## 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
``````

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

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

``````new(n : int, k : int) =
``````

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

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

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

``````override this.ToString() : string =
``````

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

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

## F# 组合库实现

``````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"
``````

``````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 同时作为输入参数和私有字段。这看起来有点不方便，因此在大多数情况下，我对参数和私有成员二者中的一种采用大写表示法。

``````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)
``````

IsLast 成员函数的定义如下：

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

``````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
``````

``````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
``````

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

``````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
/ bigint i
``````

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

## 使用 CombinatoricsLib

``````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"

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

// end program
``````

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

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

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