階乗進法

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。　今回は、階乗進法 (factorial representation) という数の表し方を見ていきます。

10進法が10を基数にしている、つまり10の累乗の級数で表されるのに対して、階乗進法は自然数の階乗の級数で表されます。　階乗進法で表された数を階乗進数と呼ぶことにします。

階乗進法の定義

階乗進数を括弧付きで添字に ${ F }$ を付けて表す（混同の心配がない場合は括弧を省略することもあります）ことにすると、 ${ n }$ 桁の階乗進数 ${ (c_nc_{n-1}\cdots c_2c_1)_F }$ は

　　 ${ \displaystyle\begin{align*} (c_nc_{n-1}\cdots c_2c_1)_F &= \sum_{m=1}^n m! \cdot c_m \\[2mm] &= n! \cdot c_n + (n-1)! \cdot c_{n-1} + \cdots + 2! \cdot c_2 + 1! \cdot c_1 \end{align*}}$

で定義されます。　具体的には以下のようになります：

　　 ${ \displaystyle\begin{align*} 332101_F &= 6! \cdot 3 + 5! \cdot 3 + 4! \cdot 2 + 3! \cdot 1 + 2! \cdot 0 + 1! \cdot 1 \\ &(= 2575) \end{align*}}$

2575 は10進数での等しい数です。

各桁の数のとりうる範囲

各桁の数 ${ c_i }$ のとりうる範囲は ${ 0 \leqq c_i \leqq i }$ です。　この範囲を超えた場合は、単に上の桁に繰り上げされます。　例えば ${ 500_F }$ という階乗進数があったとすると、定義より

　　 ${ \displaystyle\begin{align*} 500_F &= 3! \cdot 5 \\ &= 3! \cdot (4 + 1) \\ &= 4! + 3! \\ &= 1100_F \end{align*}}$

となります。　各桁で上限の数が異なるので注意が必要。

10進数と階乗進数との相互変換

階乗進数から10進数への変換は、階乗進数の定義に従って計算すれば求まります。　一方、10進数から階乗進数への変換は、 ${ n! }$ で割って余りを求めていってもいいんですが、10進数を2進数などに変換するときに使う筆算の方法と同様のやり方があります。　少し違うところは割る数が1ずつ増えていくところです。　たとえば10進数の 2575 を階乗進数へ変換するには以下のようにします：

　　 ${ \displaystyle\begin{align*} \begin{array}{rr} 1) & 2575 & \\ \hline 2) & 2575 & \\ \hline 3) & 1287 & \cdots 1 \\ \hline 4) & 429 & \cdots 0 \\ \hline 5) & 107 & \cdots 1 \\ \hline 6) & 21 & \cdots 2 \\ \hline 7) & 3 & \cdots 3 \\ \hline & 0 & \cdots 3 \end{array} \end{align*}}$

商が0になるまで続け、最後に右の余りを下から並べて ${ 332101_F }$ とすると求める階乗進数になります。　7で割った余りが6!の桁の数になるなど、割る数とその桁がずれているので注意。

最初の1での割り算は実質的に必要ありませんが、並び的に書いてみました。　1で割った余りは常に0で、0! の桁の数字が常に0（範囲的にも ${ 0 \leqq c_0 \leqq 0 }$ より ${ c_0 = 0 }$ で一貫している）と解釈することもできますが、桁の数がおかしくなるので書かない方がいいかもしれません。

上記の計算で行った割り算を「（割られる数）=（割る数）×（商）+（余り）」の関係を使って書き表すと、元の数 2575 は

　　 ${ \displaystyle\begin{align*} 2575 = 1 \cdot (2 \cdot (3 \cdot (4 \cdot (5 \cdot (6 \cdot (7 \cdot 0 + \textbf{3}) + \textbf{3}) + \textbf{2}) + \textbf{1}) + \textbf{0}) + \textbf{1}) \end{align*}}$

となり、太字の部分に階乗進数の各桁の数が現れます。　この表式は階乗進数を10進数に変換するコードを再帰的に書くのに使えます。

階乗進法で表すことのできる最大の数

${ n }$ 桁で表せる最大の階乗進数は ${ n(n-1)\cdots 21_F }$ です。　これを10進数で表すと

　　 ${ \displaystyle\begin{align*} &n(n-1)\cdots 21_F \\ &\quad= n! \cdot n + (n-1)! \cdot (n-1) + \cdots + 2! \cdot 2 + 1! \cdot 1 \\ &\quad= n! \cdot \left\{(n+1) - 1\right\} + (n-1)! \cdot (n - 1) + \cdots + 2! \cdot (3 - 1) + 1! \cdot (2 - 1) \\ &\quad= \left\{(n+1)! - n!\right\} + \left\{n! - (n-1)!\right\} + \cdots + \left\{3! - 2!\right\} + \left\{2! - 1!\right\} \\ &\quad= (n+1)! - 1 \end{align*}}$

となります。　ちなみに ${ n }$ 桁以下の階乗進数でで表すことができる正の数の個数は同じく ${ (n+1)!-1 }$ で、0以上の数の個数は ${ (n+1)! }$ となります。

階乗進数についての算数はこれくらいにしておいて、次は階乗進法に関するコードを書いていきます。

実装

階乗進法に関連するコードとして、階乗進数と10進数を相互に変換するコードを書いて見ましょう。　階乗が絡んでいるので再帰的なコードを書く練習には適しています。

準備

まずは階乗進数を表すクラスを定義しておきましょう。　このクラスは各桁の数を coefficients として Seq[Int] 型で保持するとします。　コンストラクタに渡される引数の Seq は head （0番目）が ${ n! }$ の桁の数となっています：

case class FactorialRepresentation(private val coefficients: Seq[Int]) {

  /** Int の可変引数コンストラクタ */
  def this(cHead: Int, cTail: Int*) = this(cHead +: cTail)

  /** n! の桁の数を返す */
  def coefficient(n: Int): Int =  coefficients(order - n)

  /** 次数（桁数） */
  def order: Int = coefficients.length

  // 各桁の数字の範囲を検証
  (order to 1 by -1).foreach { i =>
    val c_i = coefficient(i)
    require(0 <= c_i && c_i <= i)
  }
}

各桁の数の範囲をチェックしてたりしてますが、まぁ、以下のようにインスタンス化できるという以外は単なる周辺実装です：

new FactorialRepresentation(3, 3, 2, 1, 0, 1)

// 以下は 2! の桁の数が範囲を超えてるので IllegalArgumentException が投げられる
new FactorialRepresentation(3, 1)

階乗進数 → 10進数

さて、アルゴリズムが関連した実装をやっていきましょう。　まずは階乗進数を10進数に変換するコード。　これは階乗進数の定義に従って計算してもいいんですが、例えば100桁の階乗進数を10進数に変換するときに、100! と 99! を別に計算するのは明らかに無駄なので、もうちょっと効率的な計算方法を採ります。

「10進数と階乗進数との相互変換」の箇所の説明で出てきた以下のような表式（ ${ 7 \cdot 0 = 0 }$ としてます）

　　 ${ \displaystyle\begin{align*} 2575 = 1 \cdot (2 \cdot (3 \cdot (4 \cdot (\underline{5 \cdot (\underline{6 \cdot (\underline{0} + 3)} + 3)} + 2) + 1) + 0) + 1) \end{align*}}$

を使って、下線部のように入れ子になった再帰的なアルゴリズムとして計算します。　ちょっと複雑ですが、やることが理解できればコードは簡単に書けて、以下のような toInt メソッドのようになります：

case class FactorialRepresentation(private coefficients: Seq[Int]) {
  ...

  /** Int 値へ変換する */
  def toInt: Int = {
    @tailrec
    def toInt(i: Int, cs: Seq[Int], n: Int): Int = n match {
      case 0 => i
      case _ => toInt((i + cs.head) * n, cs.tail, n-1)
    }

    toInt(0, coefficients, order)
  }
}

ローカル関数の toInt で、i が返り値となるアキュムレータです。　これを実際に使ってみると

assert( new FactorialRepresentation(1, 2, 0, 1).toInt       == 37 )
assert( new FactorialRepresentation(3, 3, 2, 1, 0, 1).toInt == 2575 )

のようになります。

10進数 → 階乗進数

次は逆に10進数から階乗進数に変換するコード。　これは筆算で行った計算をそのままコードに直せば OK です。　FactorialRepresentation コンパニオンオブジェクトに fromInt(Int) メソッドとして定義しましょう：

object FactorialRepresentation{

  /** Int 値から変換する */
  def fromInt(i: Int): FactorialRepresentation = {
    @tailrec
    def divide(dividend: Int, divisor: Int, cs: Seq[Int]): Seq[Int] = dividend match {
      case 0 => cs
      case _ => divide(dividend / divisor, divisor + 1, (dividend % divisor) +: cs)
    }

    val cs = divide(i, 2, Nil)
    new FactorialRepresentation(cs)
  }
}

ローカル関数 divide で、dividend は被除数（割られる数）、divisor は除数（割る数）です。　再帰の度に divisor を1ずつ増やしてるところが階乗進数のアルゴリズム。　これを変化させずに2を使えば2進数が得られたりします。　使うのは簡単：

import FactorialRepresentation._

assert( fromInt(37)   == new FactorialRepresentation(1, 2, 0, 1) )
assert( fromInt(2575) == new FactorialRepresentation(3, 3, 2, 1, 0, 1) )