置換の符号 - 倭算数理研究所

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。　今回は指定された置換の符号を計算するアルゴリズム。　ここでは Java や Scala のコードで扱い易くするため、n 個の置換は1から n の整数ではなく、0から n-1 の整数で指定することにします。　例えば6つのモノの置換（のうちの1つ）は

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

などとなります。

『Java によるアルゴリズム事典』を見ると、頑張って互換（２つのモノの置換）を繰り返していくしかないようですね。　もっと代数的な計算でサクッと出す方法ないのかなぁ（笑）

実装コード

ここでは Permutation というクラスを作って、そのクラスに sgn プロパティを定義し、その初期処理で符号を計算できるようにします。

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

  require(suffices.length > 0)
  require(suffices.indices.forall(suffices contains _))

  lazy val sgn: Int = {
    @tailrec
    def calculateSign(sign: Int, seq: Seq[Int], n: Int): Int = seq match {
      case _ if seq.length == 1 => sign
      case _ if seq.head == n => calculateSign(sign, seq.tail, n+1)
      case _ =>  // case for args: seq = Seq(2, 4, 1, 5, 3), n = 1
        val i = seq.indexOf(n)  // i = 2
        val (first, second) = seq.splitAt(i)  // first = Seq(2, 4), second = Seq(1, 5, 3)
        val newSeq = first.tail ++: first.head +: second.tail
        // newSeq = Seq(4, 2, 5, 3) ( = Seq(4) ++: 2 +: Seq(5, 3))
        calculateSign(-sign, newSeq, n+1)
    }

    calculateSign(1, suffices, 0)
  }
}

object Permutation{

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

Permutation クラスはコンストラクタ引数 suffices （Seq[Int] 型）で、上で書いた置換表記の下の段の整数のリスト Seq(0, 2, 4, 1, 5, 3) を受け取り、保持します。　Permutation コンパニオン・オブジェクトでは Permutation オブジェクトの生成を簡単にする apply() メソッドを定義しています。

置換の符号の計算は、ローカル関数 calculateSign() で再帰的に行います。　この関数の引数は

sign: Int はこの位置までの符号。　末尾再帰のためのアキュムレータ*1。
seq: Seq[Int] はまだ並び替えられていない Seq の残り部分。　互換によって 0, 1, 2, ... の順に並び替えられた部分は保持している必要がないので、この list はだんだん短くしていきます。
n: Int は次に互換によって先頭にもってくる整数。　suffices プロパティの Seq にとっては、次に n 番目の要素を n にする。

としています。　処理の分岐は引数の seq に対して

要素が1つなら sign を返す。
要素が2つ以上なら
- seq の最初の要素が n と等しいなら、符号をそのままで、seq.tail を次の seq、n を1増やして再帰する。
- seq の最初の要素が n と異なるなら、符号を反転して、seq の head と n を入れ替えてそのリストの tail を次の seq、n を1増やして再帰する（上記のコードはこれをそのままはやってませんが）。

最後のケースはちょっと分かりにくいですが、例えば引数が seq = Seq(2, 4, 1, 5, 3), n = 1 となっていたら、2と1を入れ替えて (1, 4, 2, 5, 3) にして、その tail (4, 2, 5, 3) を次の list にします。

なんか、コードに簡単なコメント入れて載せただけの方が分かりやすいかもしれませんね。

実行

上記のコードを実際に動かしてみましょう。　~~あまりコンストラクタを使いやすくしてないので Permutation のインスタンス化が面倒ですが。~~ Permutation コンパニオン・オブジェクトを導入して、少々インスタンス化を簡単にできるようにしました：

val p0 = Permutation(0, 2, 1)
assert(p0.sgn == -1)

val p1 = Permutation(0, 3, 2, 1)
assert(p1.sgn == 1)

val p2 = Permutation(0, 2, 4, 1, 5, 3)
assert(p2.sgn == 1)

まぁ、こんなもんでしょう。

【修正1】

当初 List を使って ListPermutation というクラスを実装してましたが、Seq を使った SeqPermutation に変更しました。

【修正2】

SeqPermutation クラスを Permutation クラスに名前を変え、towards プロパティを suffices プロパティに変更しました。　また、Permutation コンパニオン・オブジェクトを作成して、Permutation オブジェクトのインスタンス化を簡単にできるようにしました。