組合せの個数　その1 - 倭算数理研究所

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。　Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ。　今回は組合せの個数を計算するアルゴリズム。　その1では、あまり実用的ではないですが、パスカルの三角形に関連する公式を使って個数を計算するアルゴリズムを見ていきます。

この記事の内容

この記事の内容
参考
アルゴリズム
実装

参考

『Javaによるアルゴリズム事典』

アルゴリズム

組合せの個数は二項係数 ${ {}_n C_r = \binom{n}{r}}$ で与えられます。　二項係数は以下の関係式を満たします：

　　 ${ \displaystyle\begin{align*} \begin{cases} {}_n C_0 = {}_n C_n = 1 \\[2mm] {}_n C_r = {}_{n-1} C_{r-1} + {}_{n-1} C_r \end{cases} \end{align*}}$

これは以下のパスカルの三角形を導きます：

n \ r	0	1	2	3	4	5	6
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1

例えば赤字で示された ${ {}_6 C_2 = 15 }$ は、左上と上のマスの青字の2つの数字 ${ {}_5 C_1 = 5,\, {}_5 C_2 = 10 }$ の和で計算できます。　また、 ${ r = 0 }$ と ${ r = n }$ のマスは全て1です。

実装

アルゴリズム　その1

まずは上記の公式をそのままコードにすると以下の様になります：

object BinomialCoefficient{

  def apply(n: Int, r: Int): Int =
    if(r == 0 || r == n) 1
    else apply(n-1, r-1) + apply(n-1, r)
}

引数のチェック（ ${ n }$ が負でないなど）はしてません。　このメソッドを使う場合は次のようにします：

assert( BinomialCoefficient(6, 2) == 15 )

この実装方法では2度 apply() メソッドを再帰的に呼び出すので末尾再帰にできません（末尾って基本1個しかないからね）。　よって大きい ${ n }$ に対しては StackOverflow を起こし得ます。

アルゴリズム　その2

二項係数の計算を末尾再帰で行うには、二項係数のうち ${ n }$ の値が一定のもの（表の行、横一列）を1つのコレクションとして、1ステップで次の ${ n }$ の行を計算するようにします。　例えば ${ n = 2 }$ の行は「1 2 1」ですが、これを使って ${ n = 3 }$ の行を計算するには前後にそれぞれ0を付けた2つのコレクションを要素ごとに足します：

0 1 2 1
1 2 1 0
-------
1 3 3 1

これを実装すると

object BinomialCoefficient{

  def apply(n: Int, r: Int): Int = {
    require(n > 0)
    require(0 <= r && r <= n)

    // 2つの Vector[Int] を要素ごとに加える
    def add(v0: Vector[Int], v1: Vector[Int]): Vector[Int] =
      v0.zip(v1).map(p => p._1 + p._2)  // zip() メソッドで各要素ごとにタプルを作って加える

    @tailrec
    def apply(accum: Vector[Int], i: Int): Vector[Int] = i match {
      case 0 => accum
      case _ => apply(add(0 +: accum, accum :+ 0), i-1)
        // 前と後ろに 0 を要素として付け加えたものを加える
    }

    apply(Vector(1), n)(r)
      // apply() で返された Vector[Int] の r 番目の要素を取得
  }

メソッドの使い方はアルゴリズムその1と同じです。　require() で事前条件のチェックなども入れてるのでちょっとコードが長くなってますが、思ったよりは簡単に書けた感じがします。

アルゴリズム　その3

上記の計算では最終的に不必要な和も計算しているので、本質的には同じだけどもう少し効率的になるようにリファクタリングしましょう。　実際にどの和が必要になるか見てみると、例えば ${ {}_6 C_2 }$ を計算するには以下の赤字と青字を併せた平行四辺形の部分だけが必要になります：

n \ r	0	1	2	3	4	5	6
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1

これを実装すると以下の様になります（事前条件 require() や add() メソッドは同じ）：

object BinomialCoefficient{

  def apply(n: Int, r: Int): Int = {
    require(n > 0)
    require(0 <= r && r <= n)

    val s = if(n-r < r) n-r else r  // r が n の半分より大きければ n-r で計算する
    if(s == 0) return 1
    if(s == n) return n

    // 2つの Vector[Int] を要素ごとに加える
    def add(v0: Vector[Int], v1: Vector[Int]): Vector[Int] =
      v0.zip(v1).map(p => p._1 + p._2)

    @tailrec
    def apply(accum: Vector[Int], i: Int): Vector[Int] = i match {
      // n = 6, s (= r) = 2 の場合
      case 0 =>             // i = 0 のケース
        accum
      case _ if i <= s =>   // 0 < i <= 2 のケース
        apply(add(accum.init, accum.tail), i-1)
      case _ if i < n-s =>  // 2 < i <= 4 のケース
        apply(add(0 +: accum.init, accum), i-1)
      case _ =>             // 4 < i <= 6 のケース
        apply(add(0 +: accum, accum :+ 0), i-1)
    }

    apply(Vector(1), n).head
      // この apply() メソッドの返り値は要素が1つの Vector[Int]
  }
}

s は公式 ${ {}_n C_r = {}_n C_{n-r} }$ を使って ${ r }$ と ${ n-r }$ のうち小さい方を使って計算するためのものです。　無駄な和を計算しないようにするためにローカル関数 apply() の match 文で場合分けが多くなってますが、やってることはあんまり変わってません。　この呼び出しの後では要素が1つしかない Vector[Int] が返されるので、head メソッドで要素を返してます。