階乗と順列の個数 - 倭算数理研究所

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。　今回は再帰関数の例としてよく出てくる自然数の階乗と、それに関連する順列の個数を計算するアルゴリズムを見ていきます。　再帰関数の例としてよく出てくると言っても、通常の API で簡単に書けるんですが。

この記事の内容

この記事の内容
参考
階乗 Factorial
二重階乗 Double Factorial
順列の個数

参考

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

階乗 Factorial

自然数 ${ n }$ の階乗 ${ n! }$ は

${ 0! = 1 }$
${ n > 0 }$ のとき、1から ${ n }$ までの自然数の積

で定義されます。　式で書くと

　　 ${ \displaystyle\begin{align*} n! = \begin{cases} 1 & (n = 0) \\ n(n-1)(n-2)\cdots 1 & (n > 0) \end{cases} \end{align*}}$

${ n > 0 }$ の場合は積の記号 ${ \prod }$ を使って

　　 ${ \displaystyle\begin{align*} n! = \prod_{i=1}^n i \end{align*}}$

と書いた方が ${ \TeX }$ 的にはラク。

Scala では、to メソッドによって Range オブジェクトが作れる型（Int や Long など）なら、Seq#product メソッドによって簡単に実装できます。　例えば Long 型に対しては

  def factorial(i: Long): Long = i match {
    case 0L | 1L => 1L
    case _ => (2L to i).product
  }

となります（引数が負の整数の場合のチェックを行ってませんけど）。

spire では整数型の spire.math.Integral に上記のような to メソッドが定義されていないので、原点に立ち返って再帰関数で書いてみましょう：

import spire.math.Integral
import spire.implicits._

def factorial[I: Integral](i: I): I = {
  require(i >= 0)

  @tailrec
  def factorial(prod: I, n: I): I = n match {
    case 0 | 1 => prod
    case _ => factorial(prod * n, n-1)
  }

  factorial(1, i)
}

今度はマジメに引数が0以上であることをチェックしてます。　ジェネリックな実装にしているので、引数の型に応じて返り値の型も変えられます：

factorial(5)  // Int 型の 120 を返す
factorial(5L)  // Long 型の 120L を返す
factorial[Long](5)  // Long 型の 120L を返す

ところで、実装した後に言うのもなんですが spire では整数型に「!」オペレータが定義されていて、「import spire.implicits._」を書いておけば階乗を簡単に計算できます：

import spire.implicits._
// import scala.language.postfixops

assert( 120 == 5! )

二重階乗 Double Factorial

1つ飛ばしの自然数の積、二重階乗（ダブル・ファクトリアル）「!!」もついでにやっておきましょう。

　　 ${ \displaystyle\begin{align*} n!! = \begin{cases} 1 & (n = 0,\,1) \\ n(n-2)(n-4)\cdots 1 & (n > 1, n: \textrm{odd}) \\ n(n-2)(n-4)\cdots 2 & (n > 1, n: \textrm{even}) \end{cases} \end{align*}}$

Scala の場合は to メソッドに加えて by メソッドで整数の間隔を指定できます：

  def doubleFactorial(i: Long): Long = i match {
    case 0L | 1L => 1L
    case _ => (i to 2L by -2).product
  }

今の場合、i が奇数だと 2L が Range オブジェクトの要素にはなりませんが、きちんと3Lまで止めてくれます。

spire の場合は階乗の場合とほとんど変わりません：

import spire.math.Integral
import spire.implicits._

def doubleFactorial[I: Integral](i: I): I = {
  require(i >= 0)

  @tailrec
  def factorial(prod: I, n: I): I = n match {
    case 0 | 1 => prod
    case _ => factorial(prod * n, n-2)  // n-2 になっただけ
  }

  factorial(1, i)
}

ちなみに spire では「!!」オペレータは定義されてないので、使いたい場合は自分で実装する必要があります。

そういえば、Java の数学ライブラリ commons-math では doubleFactorial は階乗の値を double 値で返す関数だったような・・・

順列の個数

n 次の順列の個数は ${ n! }$ ですが、部分順列*1（n 個の中から r 個のモノを選んで並べる）の個数は、高校数学でやるように ${ {}_n P_r }$ となります：

　　 ${ \displaystyle\begin{align*} {}_n P_r &= \frac{n!}{(n-r)!} = n(n-2)(n-4)\cdots(n-r+1) \\ &= \prod_{i=n-r+1}^n i \end{align*}}$

Scala による実装はこんな感じ：

  def permutationCount(n: Long, r: Long): Long = r match {
    case 0L => 1L
    case _  => (n until (n - r) by -1).product

相変わらず引数の事前条件をチェックしていないのでちょっと気持ち悪いですが。　積に ${ n-r }$ は含めないので to メソッドではなく until メソッドを使っています。

次は spire による実装：

import spire.math.Integral
import spire.implicits._

def permutationCount[I: Integral](n: I, r: I): I = {
  require(n >= 0)
  require(0 <= r && r <= n)

  @tailrec
  def permutationCount(prod: I, n: I, r: I): I = r match {
    case 0 => prod
    case _ => permutationCount(prod * n, n-1, r-1)
  }

  permutationCount(1, n, r)
}