全置換の生成

『Java によるアルゴリズム事典』には載ってなかったんですが、n 個のモノの全置換を生成するコードを見ていきます（目次）。

Scala では List などの順序付きのコレクション（正確には scala.collection.SeqLike トレイトのサブ型）では permutations() メソッドによって全置換を生成することができるのですが、コードを見るとガッツリ var を使った Iterator を書いてたので（別にいいんですけど）、ここでは再帰関数を使って書いてみます。　あと、置換を取得したあとで頻繁に置換の符号を使う場合、生成の段階で符号もシステマティックに計算できればちょっとコストが軽減できるかもしれません。

実装コード

まずは置換の符号のことは気にせずに、全置換の生成だけを考えましょう。　再帰を使って生成するには、n 個の置換を n-1 個の置換から作ればよさそうなので、例えば5個の置換の1つ [02413]*1 に対して「5」を

[ 0 2 4 1 3 ]
 ^ ^ ^ ^ ^ ^

の6箇所のそれぞれに挿入してやれば6個の置換が6個作れますね。　これを踏まえて、全置換を生成するコードを書いて見ましょう。　置換を表すトレイト Permutation やその実装クラス ListPermutation は飾りです。　生成コード内部では Permutation オブジェクトを直接使わず、List[Int] オブジェクトを扱ってます。

/** 置換のトレイト */
trait Permutation{
  def sgn: Int
}

/** Permutation の実装クラス */
class ListPermutation(private to: List[Int]) extends Permutation{
  lazy val sgn = ???  // 「置換の符号」の記事参照
  override def toString: String = to.mkString("[", " ", "]")
}

/** Permutation のコンパニオンオブジェクト */
object Permutation{

  def permutations(degree): Seq[Permutation] = {
    require(degree > 0)

    @tailrec
    def generatePermutations(seq: Seq[List[Int]], n: Int): Seq[List[Int]] =
      n match {
        case 1 => seq
        case _ =>
          val e = degree-n+1  // 挿入する整数
          val newSeq = seq.flatMap{ list =>
            (e to 0 by -1).map{ i =>
              // i 番目に e を挿入
              val (first, second) = list.splitAt(i)
              first ::: e :: second
          }
          generatePermutations(newSeq, n-1)
      }

    generatePermutations(Stream(List(0)), degree).map(new ListPermutation(_))
      // 第1引数には遅延評価の Seq が必要
  }
}

置換の生成はローカル関数 generatePermutations() メソッドを再帰的に呼び出して行います。　この関数の引数は

• seq: Seq[List[Int]] はある定まった次数（何個のモノの置換か）の全置換の Seq です。　この各要素の List[Int] に対して上述の挿入を行って次の generatePermutations() に渡します。
• n: Int は再帰を行う残り回数(-1)です。　n は最終的に取得したい置換の次数から始まって再帰の度に1ずつ減らしていきます。

となっています。　再帰は n が1になれば seq を返して終了します。

n が2以上のときの処理は上記の説明の通りですが、一応説明。

変数 e は、上記の説明でいう「5」にあたるものです。　各 List[Int] に対して複数個の List[Int] を新たに生成するので seq に対して flatMap を呼び出して Seq を平坦化しています。　実を言うと、generatePermutations() が末尾再帰になっていても、正格評価の（遅延評価でない）Seq は置換の次数が少々大きくなっただけで、この flatMap() が StackOverflow を起こします。　なので、generatePermutations() の実際の呼び出し箇所では遅延評価の Stream(List(0)) を渡しています。

「(e to 0 by -1)」は e から始まって1ずつ減らして0まで走る範囲 (Range) です。　普通に (0 to e) でもいいんですが、このようにしておくと一番最初に恒等置換 [0 1 2 ...] が返されます。

実行　その1

上記のコードの実行は簡単。　次数6の全置換を表示するには以下のようにします。

Permutation.permutations(4).foreach(println)

結果は

[0 1 2 3]
[0 1 3 2]
[0 3 1 2]
[3 0 1 2]
[0 2 1 3]
 ...

「3」が前に進んでいく感じ。

同時に符号を計算する実装

次は全置換の生成に加えて、置換の符号も同時に計算するような実装を考えてみましょう。　置換の生成に関しては上記と同じ。　で、置換の符号のシステマティックな計算ですが、これは案外簡単にできて、新たに挿入する整数が

• 最後に挿入される場合は符号を変えない
• 1つ前に挿入される毎に符号が変わる

となります。　例えば [02413] の符号は -1 ですが、ここに「5」を挿入するとき

• [024135] ・・・ 符号は [02413] と同じ -1
• [024153] ・・・ 符号は変わって 1
• [024513] ・・・ 符号はそのまま -1
• [025413] ・・・ 符号は変わって 1
• ...

となります。　最初のものは恒等置換にするのに「5」を移動させる必要がないことから分かり、それ以降のものは互換によって「5」を前に進めていくと思うと分かりやすいかと思います。

さて、これを実装しましょう。　Permutation の実装クラスは ListPermutation から変更して SignedPermutation にしています。　これは List[Int] と置換の符号の Int を保持するクラスと思っても OK。　ついでに、置換の生成コードのメイン部分を SignedPermutation クラスの generateHigherPermutations() メソッドに移しています。

trait Permutation{
  def degree: Int
  def sgn: Int
}

object Permutation{

  def permutations(degree: Int): Seq[Permutation] = {
    require(degree > 0)

    @tailrec
    def generatePermutations(seq: Seq[SignedPermutation], n: Int): Seq[SignedPermutation] =
      n match {
        case 1 => seq
        case _ =>
          val newSeq = seq.flatMap(_.generateHigherPermutations)
          generatePermutations(newSeq, n-1)
      }

    val p1 = new SignedPermutation(List(0), 1)
    generatePermutations(Stream(p1), degree)
  }

  private[Permutation] class SignedPermutation(private val to: List[Int], val sgn: Int)
      extends Permutation{

    override def degree = to.length

    def generateHigherPermutations: Seq[SignedPermutation] =
      (degree to 0 by -1).map{ i =>
        val (first, second) = to.splitAt(i)
        val newTo = first ::: degree :: second
        val newSign = if((degree-i) % 2 == 0) sgn else -sgn
        new SignedPermutation(newTo, newSign)
      }

    override def toString: String = to.mkString("[", " ", "]")
  }
}

ちょこちょことコードを変えてる箇所がありますが、符号を計算する「val newSign = ...」のところ以外は本質的に同じです。

実行　その2

コードの使い方はその1と同じ。　せっかく符号も一緒に計算したので、表示されるようにしてみましょう：

Permutation.permutations(4).map(p => s"$p : ${p.sgn}").foreach(println)

結果は

[0 1 2 3] : 1
[0 1 3 2] : -1
[0 3 1 2] : 1
[3 0 1 2] : -1
[0 2 1 3] : -1
 ...

となります。　ほんとは符号計算なしバージョンとか Scala の SeqLike#permutations メソッドとパフォーマンスを比べたらいいんでしょうけど、面倒なので終了。

Scala や Groovy ではデフォルトで全置換を生成するメソッドが定義されてるので自分で書くのは大変なのかなぁと思ってたけど、案外簡単に書けて充実。　まぁ、パフォーマンスとかメモリ消費とかを考えると提供されてるメソッドを使うのが無難だとは思いますがね。

修正

置換を () で囲って書いてましたが、循環置換と間違うといけないので [ ] に変更しました（コードも）。

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

*1:ここでの括弧 [] は単に (0 → 0, 1 → 2, 2 → 4, 3 → 1, 4 → 3) の置換という意味です。