May 2010

Volume 25 Number 05

テストの実行 - F# での組み合わせと順列

James McCaffrey | May 2010

サンプル コードのダウンロード

組み合わせと順列を理解しておくことは、ソフトウェア テストの基本スキルです。今月の「テストの実行」コラムでは、新しい F# 言語で記述したコードを使用して、組み合わせと順列を処理する方法を説明します。

数学の組み合わせとは、n 個のアイテムの集合から k 個のアイテムを、アイテムの順序に関係なく選択した部分集合のことです。たとえば、n = 5、k = 2 とすると、5 個のアイテムから 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} と同じと見なされるため、上記の一覧には含まれていません。また、5 個のアイテムから一度に 2 個のアイテムを選択した場合の 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}

組み合わせと順列の処理で重要な 2 つの関数は、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# のデモ アプリケーションをホストしていますが、コマンド シェルでも同じように簡単にホストできます。また、Windows PowerShell のスタートアップ スクリプトを変更して、自動的に CombinatoricsDemo.exe プログラムの場所に移動するようにしました。

図 1 F# での組み合わせと順列

デモ プログラムでは、CombinatoricsLib という F# のコード ライブラリを自動的に参照して呼び出します。デモ プログラムでは、まず、5 個のアイテムから一度に 3 個のアイテムを選択する数学的組み合わせをすべて一覧します。次に、ヘルパー メソッドを使用して、最後の組み合わせ要素 {2,3,4} を文字列の配列 {ant, bat, cow, dog, elk} に当てはめ、{cow, dog, elk} という配列を生成します。つまり、元の集合でインデックス値がそれぞれ 2、3、および 4 の位置にある 3 つの文字列の組み合わせを生成します。

続いて、Choose(200,10) の値を計算して表示します。これは、200 個のアイテムの集合から 10 個のアイテムを順序に関係なく選択した場合の数です。

さらに、Factorial(52) の値を計算して表示します。これは、1 組 52 枚のトランプのカードを並べ方の総数です。計算結果が莫大な数値になっていることに注目してください。これから説明するように、F# には、任意の大きさの整数値を処理できる機能が備わっています。

最後に、序数 n = 3 の数学的順列をすべて一覧します。

ここからは、CombinatoricsLib モジュールの F# コードと、図 1 で実行している F# のデモ プログラムのコードについて詳しく説明していきます。また、組み合わせと順列の処理に関して、F# の使用法を Visual Basic や C# などの他の言語と比較します。

今月のコラムは、C# などの .NET 言語に関して初級から中級程度の経験があり、F# のごく基本的な知識がある方を対象としています。しかし、F# がまったく初めての方でも、それほど苦労することなく理解できるのではないでしょうか。

F# の CombinatoricsLib ライブラリ

組み合わせ論ライブラリを作成するために、F# 言語とツールが組み込まれている Visual Studio 2010 beta 2 を使用しました。ここで示す F# コードは、大きな変更を加えなくても Visual Studio 2010 のリリース バージョンで機能すると予想しています。以前のバージョンの Visual Studio をお使いの場合は、マイクロソフトの F# Developer Center (msdn.microsoft.com/fsharp、英語) から F# のツールを入手できます。Visual Studio 2010 には、F# 言語だけでなく、このライブラリで使用する Microsoft .NET Framework 4 も付属しています。

ライブラリを作成するために、Visual Studio 2010 を起動して、[File] (ファイル) メニューの [New] (新規作成) をポイントし、[Project] (プロジェクト) をクリックしました。[New Project] (新しいプロジェクト) ダイアログ ボックスで、[F# Library] (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

ライブラリのコードの冒頭には、ライブラリの名前を Module1 に設定する、Visual Studio によって生成されたコードがあります。いつもなら、コラムの後半でライブラリにアクセスする構文がわかりやすくなるように名前に変更するのですが、今回のコラムではあまり特徴のない既定の名前をそのまま使用しました。

次に、トップレベルの System 名前空間と新しい System.Numerics 名前空間に F# の open ステートメントを 2 つ追加して、クラス名を完全修飾しなくてもこれらの名前空間のクラスにアクセスできるようにします。System.Numerics 名前空間は .NET Framework 4 に付属し、任意の大きさの整数値を処理できるようにする BigInteger の定義が含まれています。

F# の型定義は、同じ概念を持つ C# のクラス定義とは異なっています。型定義には、次のように、型のプライマリ コンストラクター用の入力引数を含むシグネチャがあります。

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

このシグネチャの意味は、「int 引数 の n (アイテムの総数)、int 引数の k (部分集合のサイズ)、および整数の配列の a ({0,1,4} など、個別の組み合わせ値) を受け取る、Combination という名前の型を定義する」ことです。

F# の型には、図 2 に示すコンストラクターなど、セカンダリ コンストラクターがオプションで含まれる場合があります。

new(n : int, k : int) =

型のプライマリ コンストラクターとは異なり、セカンダリ コンストラクターでは明示的に new キーワードを使用することに注意してください。このセカンダリ コンストラクターでは、n と k の値だけを受け取ります。C# などの他のプログラミング言語では、より単純なコンストラクターをプライマリ コンストラクターとして、引数を受け取るコンストラクターより前に定義するのが一般的ですが、F# ではコードからわかるように、複数のコンストラクターを持つ型の場合、最も多くのパラメーターを受け取るコンストラクターをプライマリ コンストラクターにする方法で型を作成することをお勧めします。Combination 型の構造には、続いて、次の 3 つのメンバー関数があります。

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

this キーワードは、呼び出し側の外部コードに公開するメンバー メソッドをバインドします。IsLast 関数は、関連付けられた Combination オブジェクトが辞書式順序で最後の要素 (n = 5 で k = 3 のときの {2,3,4} など) の場合、true を返します (図 1 参照)。

Successor 関数は、辞書式順序で現在の要素の次に含まれる Combination 要素を返します。

ApplyTo 関数は、文字列の配列を受け取って、現在の Combination 要素に対応する文字列の配列を返します。

型の次のメンバー関数は、Combination 要素を表示する手段を提供します。

override this.ToString() : string =

ここでは、override キーワードを使用して、カスタムの ToString 関数と基本の ToString メソッドを区別しています。F# は .NET 言語なので、すべてのオブジェクトは、ToString メソッドを含む共通基本オブジェクトの Object から継承します。オーバーライドした ToString 関数のスコープはパブリックですが、member キーワードを使用していないことに注意してください。

Combination 型の最後の 2 つのメンバー関数として Choose 関数と Factorial 関数を定義します。

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

どちらも静的関数です。つまり、これらの関数は、Combination オブジェクトの特定のインスタンスではなく Combination 型のコンテキストに関連付けられ、このコンテキストから直接呼び出されます。また、どちらの関数も BigInteger 型を返します。この型は、System.Numerics 名前空間で定義され、既定で F# コードに直接公開されます。

Combination 型に加えて、Permutation 型も定義します (Figure 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 という名前の int 型の配列を作成して 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 関数を作成するもう 1 つの手法として、.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

このライブラリでは、数字の文字列が Combination オブジェクトと Permutation オブジェクトのいずれを表しているかを特定できるように、Combination 要素を ^ (キャレット、英文字では c) 記号で区切り、Permutation 要素を % (パーセント、英文字では p) で区切ることにしました。

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 関数を処理する代わりに、ここでは 2 点の改良を加えています。まず、Choose(n, k) = Choose(n, n-k) となる点を利用します。たとえば、Choose(9,6) = Choose(9,3) となります。次に、(それぞれの結果が莫大な値になる可能性がある) 3 つの階乗を個別に処理する代わりに、一連の部分積を処理します。int 値を明示的に BigInteger 型に変換するには、F# に組み込まれている bigint 関数を使用します。

Permutation 型の実装は、Combination 型の実装と非常によく似ています。CombinationLib ライブラリの完全なソース コードは、マイクロソフトのコード ギャラリー Web サイト (code.msdn.microsoft.com、英語) から入手できます。

CombinatoricsLib ライブラリを使用する

ここでは、CombinatoricsLib ライブラリの関数を呼び出して図 1 のプログラムを作成する方法について説明します。まず、Visual Studio 2010 を起動して、CombinatoricsDemo という F# アプリケーション プロジェクトを新しく作成します。プログラム全体を図 4 に示します。

図 4 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"
  Console.ReadLine() |> ignore

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

// end program

ここでは、コードを記述する前に、Visual Studio のソリューション エクスプローラーでプロジェクト名を右クリックして、コンテキスト メニューの [Add Reference] (参照の追加) をクリックし、[Browse] (参照) タブをクリックして、CombinatoricsLib.dll アセンブリへの参照を追加します。

デモ プログラムのコードでは、まず System アセンブリと Module1 アセンブリに対する open ステートメントを追加します。CombinatorcsLib のモジュール名が Module1 のままにしていたことを思い出してください。すべてのプログラム ステートメントを try/with ブロックでラップし、例外をキャッチして処理します。セカンダリ コンストラクターを使用して Combination オブジェクトのインスタンスを作成し、5 個のアイテムから一度に 3 個のアイテムを選択する数学的組み合わせの最初のオブジェクト ({0,1,2}) を作成し、c という名前を付けます。ここで、F# の便利な %A という書式指定子を使用します。%A の機能は、Combination オブジェクトの表示方法を推論するよう F# に指示することです。また、%s という文字列書式を使用することもできます。

次に、F# の while..do ループを使用して、Combination(5,3) の要素を 10 個すべて反復処理して表示します。反復処理が終了すると Combination オブジェクトの c が最終要素となるため、ApplyTo 関数を呼び出してこの組み合わせを文字列の配列に当てはめます。

Choose 関数と Factorial 関数を Combination 型の c オブジェクトではなく Combination 型のコンテキストから呼び出していることに注意してください。同様にして Permutation 型のコードを呼び出したら、デモ プログラムの最後で Console.ReadLine メソッドを使ってユーザー入力を待機して停止し、このメソッドの戻り値を組み込みの ignore オブジェクトにパイプします。with ブロックでは例外を処理しますが、ここでは例外エラー メッセージを表示するだけです。

ここまでの説明のように F# プログラムから F# ライブラリを呼び出すだけでなく、任意の .NET 準拠言語から F# ライブラリを呼び出すことができます。また、Visual Studio では、便利な F# Interactive (F# 対話型) ウィンドウを使用して、アドホックに呼び出すことができます (図 5 参照)。

図 5 F# ライブラリの対話的な使用

画面の下部の F# Interactive ウィンドウでは、次の形式のコードを入力して CombinatoricsLib アセンブリの参照を追加しています。

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

ここでは、#r で参照の追加を表し、;; を入力して F# ステートメントを終了しています。これで、ライブラリの関数を対話的に呼び出せるようになりました。すばらしいですね。

私見ですが、F# の使用には長所と短所があります。短所は、予想以上に F# の習得が難しかったことです。関数型のスタイルで記述することは、私にとって大きなパラダイム シフトでした。また、他の言語よりも顕著な性質として、F# には 1 つの処理を実行する方法が複数用意されているため、自身の F# コードが最適な方法で記述されているかどうか不安に感じました。

しかし、少なくとも私の場合は、F# の習得によるメリットがコストを確実に上回っていると感じています。経験豊富な F# 開発者に聞いたところ、ほとんどの開発者は、処理のコードを記述する方法は確かに複数用意されているけれども、採用する手法は技術の効率性の問題というより個人の好みの問題の方が多いと述べていました。また、F# の構文とコーディングのパラダイム (既定で変更不可である点など) に取り組んだことで、C# などの手続き型言語でのコーディングに関して理解を深められたと感じました。

Dr. James McCaffrey は Volt Information Sciences, Inc. に勤務し、ワシントン州レドモンドにあるマイクロソフト本社で働くソフトウェア エンジニアの技術トレーニングを管理しています。これまでに、Internet Explorer、MSN サーチなどの複数のマイクロソフト製品にも携わってきました。また、『.NET Test Automation Recipes』(Apress、2006 年) の著者でもあります。連絡先は jammc@microsoft.com (英語のみ) です。

この記事のレビューに協力してくれた技術スタッフの Brian McNamara、Paul Newson、および Matthew Podwysocki に心より感謝いたします。