順列の辞書順序による番号付け～階乗進法編～

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。　今回は順列に辞書順序で番号を付けたとき、与えられた順列とその番号との相互の変換を考えます。　ただし番号は Int などの通常の整数値ではなく、階乗進法で表された数字であるとします。　階乗進法については以前の記事参照。

この記事中では ${ n }$ 個のモノの順列（ ${ n }$ 次の順列）は0から ${ n-1 }$ の並びで表すことにします。　例えば、6次の順列（の1つ）は

　　 ${ \displaystyle\begin{align*} \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 0 & 5 & 4 & 2 \end{pmatrix} \end{align*}}$

などとなります。　この順列の略記法として、下段の数字を取り出して [310542] と書くことにします。　また、順列に付けた番号は0から始まることとします。　6次の順列の0番目は [012345]、1番目は [012354] などとなります。

階乗進法で表した数字（階乗進数）は、右下に F を付けて10進数と区別することにします。

順列 → 番号（階乗進数）

まずは順列が与えられたときに番号を計算するアルゴリズムを見ていきましょう。　これは高校数学で辞書順序の問題をやるときにする計算です。

アルゴリズム

具体例で見ていく方が分かりやすいと思うので、6次の順列 [310542] について計算手順を見ていきましょう。　順列の番号が0から始めることにしたので、ある順列の番号はその順列より辞書順序的に小さい順列の個数と一致します*1。　したがって、[310543] より小さい順列の個数を数えればいいことになります。

この個数を数えるには樹形図を描くと分かりやすいかもしれませんが、ちょっと（イヤものすごく）面倒なので、別の（たぶん高校数学でも使われる）方法で数えましょう。　順列の数字の並びで、アンダーバー (_) を使って適当な数字を入れる場所を表すことにして、[310452] より小さい順列の個数を数えると

0 _ _ _ _ _   5! 個 \
1 _ _ _ _ _   5! 個  〉 5!･3 個
2 _ _ _ _ _   5! 個 /
3 0 _ _ _ _   4! 個 〉4!･1 個
  1 0 2 _ _   2! 個 \ 2!･2個
      4 _ _   2! 個 /
      5 2 _   1! 個 〉1!･1 個
        4 2

となって、[310542] より小さい順列、したがって番号は

　　 ${ \displaystyle\begin{align*} 5! \cdot 3 + 4! \cdot 1 + 3! \cdot 0 + 2! \cdot 2 + 1! \cdot 1 = 31021_F \end{align*}}$

となります。　アンダーバーの部分の個数が階乗で表されるので、階乗進法を使うと番号を比較的簡単に表すことができる、という所から階乗進法が出てきてます。

さて、階乗進法が出てきた理由はそれだけですが、その係数（階乗進数の各桁の数字）がどのように決まるかを考えてみると、「その数字より小さい（0以上の）自然数の個数（つまりはその数自身）」から「順列でその数より左に出てきているその数より小さいものの個数」を引いた数になっています。　たとえば、[310542] の4に着目すると、それより左にある4より小さい数は0,1,3の3個なので、4-3=1より、番号の階乗進数 ${ 3102\textbf{1}_F }$ の1!の係数は1となります。　順列の右端の数字（今の場合2）に対してこの計算をすると、この順列に限らず常に0になります。　これは0!の係数とみなせますが、まぁ階乗進法では書かないので無視して構いません。

ちなみに、変換前後を図で表すとこんな感じ：

      ●
      ● ●
○     ● ●
○     ○ ● ●
○ ○   ○ ○ ●
------------
3 1 0 5 4 2
     ↓
3 1 0 2 1(0) F

白丸、黒丸を併せたものが順列、そこから黒丸と取り除いて白丸だけにしたものが階乗進数です。

実装

では、これをコードに落とし込んで見ましょう。　上記の数え方では順列の左から個数を数えてましたが、手順としては右から（というかどこから）数えていっても問題ありません。　下記のコードでは、コレクションで自分より小さいものを数えるときに使う count() メソッドを上手く使うために、右から数えつつ、再帰の度にコレクションを短くしていってます。　また、init/last を使うので Vector 型を使ったりしてます。　まぁ、あくまで実装例なのでもっと上手く実装する方法があるのかもしれませんが。

番号を返すメソッドは Permutation クラスに sequenceNumber メソッドとして実装します。　返り値は階乗進数を表す FractionalRepresentation クラス*2にしてます：

class Permutation(val suffices: Seq[Int]){

  // ↓ 以下のコメントは suffices が Seq(3, 1, 0, 5, 4, 2) を返す場合（順列 [310542] の場合）

  /** 順列の辞書順序での番号を、階乗進数として返す。　番号は0から始まる。 */
  def sequenceNumber: FactorialRepresentation = {
    @tailrec
    def sequenceNumber(fact: List[Int], suffices: Vector[Int]): List[Int] =
      suffices.isEmpty match {
        case true  => fact
        case false =>  // 次の引数の場合: fact = Nil, suffices = Vector(3, 1, 0, 5, 4)
          val (init, last) = (suffices.init, suffices.last)
            // init = Vector(3, 1, 0, 5), last = 4
          val n = last - init.count(_ < last)  // n = 4 - 3 = 1
          sequenceNumber(n::fact, init)  // 次の呼び出しの引数: List(1), Vector(3, 1, 0, 5)
      }

    val fact = sequenceNumber(Nil, suffices.toVector.init)  // towards の最後の要素は削除
    FactorialRepresentation(fact)  // FactorialRepresentation オブジェクトのインスタンス化
  }
}

object Permutation{

  def apply(suffices: Int*) = new Permutation(suffices.toVector)
}

階乗進数を表す FactorialRepresentation には、コンパニオン・オブジェクトにインスタンス化のためのファクトリ apply() メソッドが定義されているとしてます。

使い方はこんな感じ：

val p = Permutation(3, 1, 0, 5, 4, 2)
assert( p.sequenceNumber == FactorialRepresentation(3, 1, 0, 2, 1) )

~~ちょっとメソッド名が長い気もしますが、~~まぁ使い方は簡単。

実装その2

『Java によるアルゴリズム事典』には、上記のコードと本質的には同じだけど、見た目が少々異なるアルゴリズムが書かれているので、なるべくそちらと同じように書いたコードも載せておきます：

class Permutation(val suffices: Seq[Int]){

  // ↓ 以下のコメントは suffices が Seq(3, 1, 0, 5, 4, 2) を返す場合

  def sequenceNumber: FactorialRepresentation = {
    @tailrec
    def sequenceNumber(fact: Vector[Int], suffices: Seq[Int]): Seq[Int] =
      suffices.length match {
        case 1 => fact  // suffices の最後の要素は無視
        case _ =>  // 次の引数の場合: fact = Vector(), suffices = Seq(3, 1, 0, 5, 4, 2)
          val a = suffices.head  // a = 3
          val seq = suffices.map(i => if(i > a) i-1 else i)
            // seq = Seq(3, 1, 0, 4, 3, 2)
          sequenceNumber(fact :+ seq.head, seq.tail)
            // 次の呼び出しの引数: Vector(3), Seq(1, 0, 4, 3, 2)
      }

    val fact = sequenceNumber(Vector(), suffices).toList
    FactorialRepresentation(fact)
  }
}

『Java によるアルゴリズム事典』にあるコードでは、順列に相当する配列（ここでは suffices にあたる）の要素をガッツリ書き換えていて副作用ありまくりですが、ここでのコードではイミュータブルなコレクションのみを使っています（よってパフォーマンスがどうなるのか計測するのが怖いですがw）。

番号（階乗進数） → 順列

次は逆に、番号（と順列の次数）が指定されたときに順列を返すコードを見ていきます。　基本的には「順列 → 番号」の場合の逆変換をすればいいんですが、1つ目の方法の逆変換をしようとすると count() を使った様な分かりやすいコードを書けずにちょっと込み入ってしまうので（単にコーディング能力のせいかもしれないけど）、ここでは2つ目の方法の逆変換、というか『Java によるアルゴリズム事典』に載ってるコードの移植で済ませます。

実装は Permutation コンパニオン・オブジェクトに nthPermutation(FractionalRepresentation, Int) メソッドとして定義します。　2つ目 Int 型の引数は順列の次数です：

object Permutation{

  def nthPermutation(n: FactorialRepresentation, degree: Int): Permutation = {
    @tailrec
    def nthPermutation(suffices: List[Int], fact: Vector[Int]): List[Int] =
      fact.isEmpty match{
        case true  => suffices
        case false =>
          // suffices = List(0, 3, 2, 1),
          // fact = Vector(3, 1) の場合
          val a = fact.last  // a = 1
          val newSuffices = a :: suffices.map(i => if(i >= a) i+1 else i)
            // newSuffices = 1::List(0, 4, 3, 2)
          nthPermutation(newSuffices, fact.init)
            // 次の呼び出しの引数:
            //   suffices = List(1, 0, 4, 3, 2), fact = Vector(3)
        }

    // n = FactorialRepresentation(3, 1, 0, 2, 1) の場合
    val fact = n.coefficientsAsNthOrderInDescendant(degree-1).toVector :+ 0
      // fact = Vector(3, 1, 0, 2, 1, 0)  ★最後に 0! の桁の 0 を付け加えておく
    val suffices = nthPermutation(Nil, fact)
    new Permutation(suffices)
  }
}

そういえば、FactorialRepresentation クラスに coefficientsAsNthOrderInDescendant(Int) メソッドというのを追加していたんでした。　これは階乗進数の係数（各桁の数）を降順で（次数の高い方から低い方へ並べて）Seq[Int] として返しますが、Seq の長さが引数の Int 値になるように高次の係数を0で埋めて返します。　つまり

val n = FactorialRepresentation(2, 1)
val cs = n.coefficientsAsNthOrderInDescendant(4)
assert( cs == Seq(0, 0, 2, 1) )

となります。　機械的な処理なのでコードは載せてませんが、まぁ難しくはないでしょう。　で、上記の nthPermutation メソッドの使い方は以下のようになります：

val n = FactorialRepresentation(3, 1, 0, 2, 1)
val p = Permutation.nthPermutation(n, 6)
assert( p == Permutation(3, 1, 0, 5, 4, 2) )

これで変換完了。

まとめ

最初は、順列の辞書順序による番号と階乗進法がどう関係してくるのかハッキリとは分かってませんでしたが、基本に立ち返って番号を計算してみると確かに階乗進法を使いたくなるような式がそのまま出てきますね。　番号を指定して順列を返すメソッドは、アルゴリズムを説明しようとすると込み入りそうだったので実装例を示しただけでしたが、もしかしたらもうちょっと示唆に富んだ説明ができるのかもしれません。

ここでは以前に作った FactorialRepresentation クラスを使って階乗進数と順列の間の変換をしましたが、既に実装した階乗進数と通常の十進数の変換を使えば、十進数と順列の間の変換も可能です。　『Java によるアルゴリズム事典』では、おそらくこれをひとまとめにしたであろう実装も書かれてます。　次回はこの十進数と順列の直接変換か、もしくは飛ばして順列の生成をやる予定。

【追記】階乗進数から順列への変換アルゴリズム

上記の内容では、階乗進数から順列への変換はコードのみを載せていて、あまりイメージの湧かない変換でしたが、もう少しやっている操作がわかる変換アルゴリズムが分かったので追記します。　ただし、上記のコードとは直接関係ありません。　また、なぜこの方法で上手くいくのかの証明もしてません。

やはり具体的な数を使って手順を説明してきましょう。　6次の順列で ${ 31021_F }$ 番目のものを取得するには、

0番目の順列 [012345] を用意する
最高次 5! の桁が3なので、上記の順列の左端から 3+1=4 個の数字を右送りに巡回させる（4番目の数は先頭へ移動） [301245]
次の次数 4! の桁が1なので、先ほどの順列の左から2つ目から 1+1=2 個の数字を右送りに巡回させる [310245]
以上を 1! の桁まで行う。

これを実際に行うと以下のようになります：

(3 1 0 2 1)_F

[0 1 2 3 4 5]
 -------
[3 0 1 2 4 5]
   ---
[3 1 0 2 4 5]
     -
[3 1 0 2 4 5]
       -----
[3 1 0 5 2 4]
         ---
[3 1 0 5 4 2]

たぶんこの方法で任意の番号の順列を求められると思いますが、どうなんでしょう？　~~あと、コード書いて試すのもちょっと面倒そうなのでやってないっす。~~　このアルゴリズムを実装してみるとこんな感じ：

object Permutation{
  
  def apply(suffices: Int*) = new Permutation(suffices.toVector)

  def nthPermutation(n: FactorialRepresentation, degree: Int): Permutation = {
    @tailrec
    def nthPermutation(suffices: Vector[Int], rest: List[Int], fact: List[Int]): Vector[Int] =
      fact match {
        case Nil => suffices :+ rest.head
        case 0 :: tail =>
          nthPermutation(suffices :+ rest.head, rest.tail, tail)
        case head :: tail =>
          // 以下の引数の場合：
          //   suffices = Vector()
          //   rest = List(0, 1, 2, 3, 4, 5)
          //   fact = List(3, 1, 0, 2, 1)
          val (first, second) = rest.splitAt(head)
            // first = List(0, 1, 2), second = List(3, 4, 5)
          nthPermutation(suffices :+ second.head, first ::: second.tail, tail)
            // 次の呼び出し：
            //   suffices = Vector(3)
            //   rest = List(0, 1, 2, 4, 5)
            //   fact = List(1, 0, 2, 1)
        }

    val cs = n.coefficientsAsNthOrderInDescendant(degree-1)
    val suffices = nthPermutation(Vector(), (0 until degree).toList, cs)

    new Permutation(suffices)
  }
}