發行項
08/13/2015

本文章是由機器翻譯。

測試回合

使用 F# 進行合併與排列

James McCaffrey

下載範例程式碼

了解合併與排列是軟體測試的基本技能。這個月 ’s 測試回合的資料行中我告訴您如何處理與組合與排列組合使用新的 F # 語言所撰寫的程式碼。

數學的組合是從一組的順序不重要的 n 個項選取 k 項目子集。對於 ex-充裕，如果 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 的五個項目組合選取兩個使用所謂字彙上的順序的每個組合元素中的值會以遞增的順序列出一次。

數學排列是所有可能的 rearrangements 的 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) 函式傳回組合的 k n 個項目從選取的項目總數。

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

例如：

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

組合及排列是研究通常簡稱為稱為組合數學或只是 combinatorics 區域的一部份。

才能看到我字形本月 ’s 欄中有一個好辦法，就是在看一下螢幕擷取畫面圖 1. 我使用 Windows PowerShell 來裝載 (Host 我 F # 示範應用程式，但可能有一樣輕鬆地使用命令殼層。修改我的 Windows PowerShell 啟動指令碼自動瀏覽到我 CombinatoricsDemo.exe 程式的位置。

圖 1組合和使用 F # 的排列組合

在幕後示範程式參考和插入 F # 程式碼程式庫的呼叫命名 CombinatoricsLib。示範開始會列出所有數學的組合，五個選取項目 3 一次。接下來，將套用至 {ant、 bat、牛、狗、 elk} 以產生 {牛、狗、 elk} 的字串陣列的最後一個組合項目 {2,3,4} 使用 Helper 方法 — 也就是三個字串從原始組位於索引值 2、 3 和 4。

我的範例程式會繼續進行運算，並顯示 Choose(200,10) 許多方法可從一組 200 順序不重要的項目選取 10 個項目值。

接下來，示範程式碼會計算並顯示的是排列 52 張牌標準紙牌花色中的牌的方法總數的 Factorial(52) 值。請注意結果是非常、非常大的值。我說明 F # 有能力處理任意大的整數值。

我的範例程式結束所列出所有的數學排列的順序 n = 3。

在各「節我將說明詳細 F # 程式碼，CombinatoricsLib 本單元和 F # 示範程式中所示在中執行程式碼圖 1. 沿著，方法我比較的使用 F # 與其他語言，例如 Visual Basic 和 C# 使用組合與排列組合。

此資料行假設您有如 C# 的.NET 語言的初級至中級經驗及使用 F # 非常基本的熟悉度。但即使您是全新 F #，您應該可以遵循我解釋不太多困難。

F # CombinatoricsLib 文件庫

若要建立我 combinatorics 媒體櫃，我使用 Visual 有 F # 語言及內建的工具的 Studio 2010 Beta 2 的發行。我相信在 F # 程式碼我在此處呈現若要使用的 Visual Studio 2010 發行版本而不需任何重大變更。如果您使用較早版本的 Visual Studio，您可以找到在「 Microsoft F # 開發 o 人 h 員 û 工 u 具 ã 」 ( F # 工具msdn.microsoft.com/fsharp). 除了 F # 語言 Visual Studio 2010 隨附在 Microsoft.NET Framework 4，我媒體櫃會使用。

我建立我的文件庫，啟動 Visual Studio 2010 並選取檔案 | 新增 | 專案。新的專案對話方塊上我選取 [F # 程式庫] 樣板，名為我媒體櫃 CombinatoricsLib。中會列出我 CombinatoricsLib 整體結構圖 2.

圖 2F # 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 我媒體櫃。我可以使用這個而 nondescript 預設名稱而非變更以敘述其性質，以便存取文件庫的語法會突顯出來，在本文稍後。

接下來，我加入了兩個 F # 開啟的最上層的 System 命名空間和新 System.Numerics 命名空間的陳述式，使我可以存取這些命名空間中的類別，而不必完整限定類別名稱。 System.Numerics 命名空間是.NET Framework 4 的一部份，並且包含 BigInteger 定義允許我處理任意大的整數值。

在 F # 中定義型別是不同的定義在概念上相等的 C# 類別。型別定義有包含主要型別建構函式輸入的引數的簽章：

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

表示這個簽章，「我正在定義名為主要的建構函式可接受 int 引數 n (總計的項目數目)，及 k (子集大小) 和整數陣列，指定等 {0,1,4} 在個別的組合值一個組合的型別」。

F # 型別可能會具有建構函選擇性次要式，如中列出一個圖 2:

new(n : int, k : int) =

請注意第二個建構函式使用明確的新關鍵字，相對於主要型別建構函式。這個第二個建構函式可以接受只針對 n 和 k 的值。與其他如 C# 程式設計語言，就可能是較簡單的建構函式做為主要建構函式也就是之前，定義接受引數的建構函式。但您為具有多個建構函式的型別在 F # 中看到它是通常最好建立一種主要的建構函式是一個含有大部分參數的型別。我的組合類型的結構會繼續進行三個成員函式：

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

在這個關鍵字會繫結至外部呼叫程式碼公開可見的成員方法。 IsLast 函式會傳回，則為 True 相關聯的組合物件最後一個項目字彙上的順序如 {2,3,4} n = 5 和 k = 3，所示圖 1.

Successor 函數會傳回字彙上的順序中的下一個複合項目至目前的項目。

ApplyTo 函式接受字串陣列，並在目前的複合項目傳回對應的字串陣列。

我下一個型別成員函式提供方法來顯示組合元素：

override this.ToString() : string =

我使用覆寫關鍵字來區分我自訂的 ToString 函式和基底的 ToString 方法。因為 F # 是一種.NET 語言，所有物件會都繼承自通用的基底物件具有 ToString 方法。請注意即使覆寫的 ToString 函式具有公用範圍，我不要使用成員關鍵字。

最後兩個成員函式組合的型別中定義選擇和 Factorial 函式：

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

這兩個函式為靜態，也就該函式是相關聯，稱為直接從組合型別，而不是組合物件的特定執行個體的內容。這兩個函式傳回型別 BigInteger，這預設 F # 程式碼直接看到 System.Numerics 的命名空間中所定義。

除了組合型別我定義排列型別中清單所示圖 2.

F # Combinatorics 庫實作

現在 let’s 超過 CombinatoricsLib 程式庫的實作詳細資料。複合主要建構函式開始：

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 關鍵字會擲回例外狀況，其中可以捕捉到由呼叫程式碼。

接下來，我設定組合的型別私用成員：

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

可以讓的關鍵字會將值繫結至私用成員。請注意我可以使用小寫 n 和 k 當兩個輸入參數，做為私用欄位。這看起來有點怪怪並因此在大部分情況下我使用大寫的標記法之參數或私用成員。

將值從輸入引數陣列複製一個轉為的型別欄位的資料會使用標準的 F # 慣用語。在 [|。 . |] 分隔符號表示可變動的陣列。次要組合建構函式會建立初始組合物件，並定義為：

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 # 中第二個建構函式必須呼叫主要的建構函式。所以我定義名為與值 0 透過 k 1 起動機 int 陣列，並連同 n 和 k 傳遞給主要的建構函式。這個 F # 機制就是為什麼最好定義為具有大部分參數建構函式的任何主要的建構函式是。

IsLast 成員函式定義為：

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

In 圖 1，請注意只有最後一個元素清單中的所有組合都有值 n-k 位於陣列的第一個位置。 F # 並不會使用明確的傳回關鍵字大部分語言一樣；默示的傳回一個函數在這種情況下是 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

我先將目前的組合物件內容的值複製到名為 temp 的可變動陣列。我接下來，定義未命名的索引變數 x，並將它放置暫存陣列的結尾。我必須使用可變動關鍵字，讓我可以遞減這個 index 變數，因為根據預設值，F # 中的大部分變數是不變。我使用 <-工作分派運算子。

一旦我找不到目前的組合物件的索引鍵的索引我遞增該值與索引鍵右邊的所有值。然後我傳遞暫存陣列現在具有到主要的建構函式之後續複合項目的值，並傳回新建立的物件。

請注意我不會傳回 null 時我是在最後一個複合項目 — 在 F # 中就會被視為不良樣式若要這麼做。我在本文中呈現的程式碼使用的樣式，並不是非常 F #-ish。 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

當在成員函式會檢查執行輸入引數時，我不需要使用，請執行關鍵字，如所需要的型別建構函式是。靜態 Array.zeroCreate 方法會建立整數陣列，初始化所有的 0 值，跟您預期的一樣。 ApplyTo 函式是很容易，因為數學搭配子集的值的範圍大小 k (0..k-1) 方式完全相同的大小 k 任何.NET 陣列索引。

覆寫的 ToString 成員函式只會建置內容物件 ’s 值所組成的字串：

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

我決定分隔具有我組合的項目 ^ (插入號) 字元會啟動與而字母] c 及分隔開頭來協助我識別是否一串數字代表一個複合或排列物件的 p 的為 %(百分比)] 字元我排列元素。

所示，是撰寫程式碼靜態 Choose 函數圖 3.

圖 3Choose 函數

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

我使用兩種最佳化代替從本文稍早所述定義運算選擇。第一次，我使用事實該選擇 (n，k) = 選擇 (n n k)。例如 Choose(9,6) = Choose(9,3)。第二個，而不是階計算三個個別乘，每一個都可能會非常大，我會計算一系列的部分產品。若要將 int 值，以鍵入 BigInteger 明確轉換，我會使用內建的 F # bigint 函數。

排列型別實作很組合型別實作相當類似。您可以從 [Microsoft 程式碼庫網站在 code.msdn.microsoft.com CombinationLib 文件庫取得 complete 原始碼。

使用 [CombinatoricsLib

本章節中我將說明如何呼叫函式來產生執行中螢幕擷取畫面所示 CombinatoricsLib 媒體櫃中圖 1. 我開始啟動 Visual Studio 2010，並建立新的 F # 應用程式專案，名為 CombinatoricsDemo。整個程式會列在 圖 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 組件。

我先示範程式碼將開啟的陳述式加入至系統] 及 [Module1] 組件。您應該還記得會 Module1 中的 [CombinatorcsLib 模組名稱。在一試 / with 區塊來擷取和處理例外狀況，包裝所有程式陳述式。我具現化組合物件，使的五個項目採取三個一次一個初始的數學組合物件 c 使用次要的建構函式：{0,1,2}. 我使用不錯 F # %A 格式規範，可指示 F # 來推斷如何列印我組合的物件。我也可能已經用 %s 字串格式。

我接下來，使用 [F # 時迴圈來逐一查看，並顯示所有 10 個 Combination(5,3) 元素。這個時候組合物件 c 是最後一個項目，然後我呼叫 ApplyTo 函式来對應到一個陣列上該組合的字串。

請注意我呼叫選擇和 Factorial 的函式，從的組合型別，而不是 c 組合物件內容。在類似的方式呼叫排列型別程式碼之後, 示範程式結束暫停供使用者輸入與 Console.ReadLine 方法我管道傳回值至內建的非好友物件的位置。我在處理中的任何例外狀況，藉由只顯示例外狀況錯誤訊息的區塊。

除了從 F # 程式呼叫的 F # 程式庫，如我示範，您可以從任何.NET 相容語言呼叫的 F # 程式庫。此外，Visual Studio 可讓您使用方便 F # 互動式視窗來進行臨機操作呼叫所示圖 5.

圖 5一個 F # 程式庫的互動使用

在 F # 互動式視窗在螢幕底部，我會藉由輸入將參考加入 CombinatoricsLib 組件：

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

在這種情況下 # r 表示加入一個參考和; 終止的互動式的 F # 陳述式。現在我可以在媒體櫃中以互動方式呼叫的函式。不錯!

在我看來有幾個優缺點來使用 F #。負邊我發現學習曲線的 F # 是比我預期較陡峭。撰寫功能性樣式中的已為我的大典範移位。而且，更多因此比其他語言 F # 有多種方式撰寫程式碼的領導我覺得 uneasy 有關是否最適當的方式撰寫我寫了任何 F # 程式碼的特定工作。

不過，在我的情況下，至少我覺得彌補成本學習 F # 絕對的好處。當對有經驗的 F # coders 說話，大部分將告訴我在許多情況下即使有事實上幾種方式若要撰寫一個工作的程式碼採用的方法是多的個人偏好技術的效率比。而且，grappling F # 語法和撰寫程式碼 (例如預設的不變性) 模範給予我我覺得是一些好洞察在程序性的語言，例如 C# 中撰寫程式碼。

Dr。James McCaffrey *適用於 Volt 資訊科學 Inc.他負責管理軟體工程師在 Microsoft 台北市，Wash.，工作校園的技術訓練。他已投入包括 Internet Explorer] 和 [MSN 搜尋數個 Microsoft 產品。Dr.McCarthy 是「.NET 測試自動化食譜」 (Apress 2006) 的作者。他可以達到在 jammc@microsoft.com. *

多虧來檢閱本文的下列的技術專家： Brian McNamara、 Paul Newson 和 Matthew Podwysocki