順列生成　その1 - 倭算数理研究所

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。　今回はある定まった次数（並べるモノの個数。　コード中では degree とする）の全順列を生成するアルゴリズムを見ていきます。　『Java によるアルゴリズム事典』には4つのアルゴリズムが載せられていますが、今回は最初のものだけをやります。　このアルゴリズムは、他の3つに比べて

辞書順序で生成できる
部分順列を生成できる
置換の符号を生成と同時に計算できる

などの利点があるので、正直このアルゴリズムをやれば他の3つは要らない気もしますが、まぁ実装的興味のため別記事で他のアルゴリズムもやる予定。　この記事では部分順列、符号の計算、重複順列もやってみます。

この記事中では、「部分順列」は高校でやる「n 個の中から r 個選んで並べる」順列を指します。　日本語ではあまり使わない言葉かもしれません。　英語で「partial permutation」と言うと、Wikipedia によれば任意の長さ（とりうる全ての r の値を含めたもの）のことを指し、ここでの部分順列は「restricted partial permutation」というようなので、この記事中での部分順列 partial permutation とは少し意味が異なるので注意。

ちなみに、Scala では List などの順序付きのコレクション（正確には scala.collection.SeqLike トレイトのサブ型）に permutations() メソッドが定義されていて、これによって全順列を生成することができるのですが、コードを見ると var を使った Iterator を書いてたので（まぁ、別にいいんですけど）、ここでは状態を持たさずに、イミュータブルなコレクションかつ再帰関数を使って書いてみます。

参考

アルゴリズム

通常、n 次の順列は1から n までの整数の並びであらわしますが、ここでは Java や Scala のコードで使いやすくするため、0から n-1 までの整数の並びで表すことにします。

今回扱う順列生成のアルゴリズムでは、使用できる数字の中から順に1つずつ選んで並べていきます。　説明のため、以下のような数字の並びのペア (,) を考えます：

(構築中の順列, 使用可能な数字)

例えば、6次の順列の構築で、構築中の順列が 034 ならば

(034, 125)

となります（これは Scala のコードではありません）。　構築を始める前は

(, 012345)

です。　さてこの表記を踏まえて、順列を構築するには「使用可能な数字」から1つ選んで「構築中の順列」の末尾に付け足し、使用可能な数字がなくなるまで続けます。　上記の (034, 125) に1度だけ構築ステップを施すと

           / (0341, 25)
(034, 125) - (0342, 15)
           \ (0345, 12)

となります。　右側の各ペアに対してまたこのステップを続けていき、使用可能な数字がなくなるとペアの左側が順列となります。　3次の順列について具体的にやってみると以下のようになります（各ステップごとに生成されるペアを「世代」と呼ぶことにしましょう）：

 第0世代   第1世代   第2世代   第3世代

                  / (01, 2) - (012, )
          (0, 12)
        /         \ (02, 1) - (021, )

                  / (10, 2) - (102, )
(, 012) - (1, 02)
                  \ (12, 0) - (120, )

        \         / (20, 1) - (201, )
          (2, 01)
                  \ (21, 0) - (210, )

「使用可能な数字」が昇順に並んでいて、構築ステップでこの数字列の左から順にとっていけば（小さいものから順にとっていけば）、結果としてできる順列は辞書順序に並びます。　この例では、第3世代のペアの左側が3次の順列になっていますが、上から順に辞書順になっていますね。

実装

順列生成のアルゴリズム自体はそれほど難しくないと思いますが、順列の総数は次数が大きくなるにしたがって組合せ論的に大きくなるので、遅延評価されるコレクションとして生成されるようにすべきでしょう。

順列を生成するメソッドを allPermutations() として、Permutation コンパニオンオブジェクトに定義することにします。　メソッドのシグニチャは以下のようにします：

object Permutation{

  def allPermutations[E](arg: Seq[E]): Seq[Seq[E]] = ???
}

アルゴリズムの説明では（0からn-1までの）整数を並べて順列にしてましたが、このメソッド宣言ではジェネリックな型 E を使って任意の型の Seq について要素を並べ替えた Seq の列を返せるようにしています。　実装もそうなるように書きます。　ただし、以下の説明ではこの型はやはり整数として行います。　このメソッドの使い方はこんな感じ:

val ps = Permutation.allPermutations(0 until 3)  // (0 until 3) ==  Seq(0, 1, 2)

assert(ps == Seq(
  Seq(0, 1, 2), Seq(0, 2, 1),
  Seq(1, 0, 2), Seq(1, 2, 0),
  Seq(2, 0, 1), Seq(2, 1, 0)))

数学の順列で通常使われる、1から n までの整数の並びによる順列は

val n = 10
Permutation.allPermutations(1 to n)

とすれば OK。

さて、では allPermutations() メソッドの実装に入りましょう。　上記のペア (構築中の順列, 使用可能な数字) はクラスとして定義しておきましょう。　名前はとりあえず Builder で：

    case class Builder(seq: Vector[E], available: Seq[E]){
      def nextGeneration: Seq[Builder] =
        available.map(e => Builder(seq :+ e, available.filter(_ != e)))
    }

case クラスとして定義していますが、コンストラクタ引数の seq と available に「val」を付けなくてもプロパティになるという以外に特に意味はありません（パフォーマンスに影響ってあるっけ？）。
seq, available プロパティがそれぞれ「構築中の順列」、「使用可能な数字」です。　「構築中の順列」には後ろから要素を追加していくので Vector 型にしてあります。　
nextGeneration メソッドは順列構築の1ステップを実行します。　返り値は Seq[Builder] です。　available から使用した要素 e を除去するのに filter メソッドを使っています。　パフォーマンス的にいいのか悪いのかよくわかりませんが・・・

さて、この Builder を使って n 世代後のペア (Builder) を遅延評価で取得するには、Stream の flatMap を使います：

    @tailrec
    def generateAll(stream: Stream[Builder], n: Int): Stream[Builder] =
      n match {
        case 0 => stream
        case _ =>
          val newStream = stream.flatMap(_.nextGeneration)
          generateAll(newStream, n-1)
      }

n 次の順列は、ペア (, 01・・・(n-1)) から初めて n 回この構築ステップを行えばいいので

  def allPermutations[E](arg: Seq[E]): Seq[Seq[E]] = {
    ...
    val start = Builder(Vector(), arg)
    generateAll(Stream(start), arg.length)  // arg.length 回ステップを繰り返す
      .map(_.seq)  // Seq[Builder] から Seq[Seq[Int]] に変換
  }

とします。　まとめると

object Permutation{

  def allPermutations[E](arg: Seq[E]): Seq[Seq[E]] = {

    case class Builder(seq: Vector[E], available: Seq[E]){
      def nextGeneration: Seq[Builder] =
        available.map(e => Builder(seq :+ e, available.filter(_ != e)))
    }

    @tailrec
    def generateAll(stream: Stream[Builder], n: Int): Stream[Builder] =
      n match {
        case 0 => stream
        case _ =>
          val newStream = stream.flatMap(_.nextGeneration)
          generateAll(newStream, n-1)
      }

    val start = Builder(Vector(), arg)
    generateAll(Stream(start), arg.length).map(_.seq)
  }
}

これで完成。　ちなみに、allPermutations() メソッドに空 Seq を渡すと、空 Seq （空 Vector）を唯一の要素として持つ Seq (Stream) を返しますが、これは数学的な定義と一致します。

リファクタリング

上記の Builder クラスと generateAll() メソッドは組合せの生成などにも使えるので、汎用化しておきましょう。　それぞれ CombinatorialBuilder トレイト, generateCombinatorials メソッドとします：

trait CombinatorialBuilder[E, B <: CombinatorialBuilder[E, B]]{
  def nextGeneration: Seq[B]
}

def generateCombinatorials[B <: CombinatorialBuilder[_, B]](start: B, n: Int): Stream[B] = {
  @tailrec
  def generateAll(stream: Stream[B], n: Int): Stream[B] =
    n match {
      case 0 => stream
      case _ =>
        val newStream = stream.flatMap(_.nextGeneration)
        generateAll(newStream, n-1)
    }

  generateAll(Stream(start), n)
}

ジェネリックに使えるようにしてあるので少々宣言が込み入ってますが、基本的には先ほどのものと変わりません。　CombinatorialBuilder トレイトには次世代を生成する nextGeneration メソッドが宣言されています。　ここに構築の1ステップを実装します。

これらのトレイト、メソッドを使って、上記の allPermutations() メソッドをリファクタリングすると以下のようになります：

object Permutation{

  def allPermutations[E](arg: Seq[E]): Seq[Seq[E]] = {

    case class Builder(seq: Vector[E], available: Seq[E])
        extends CombinatorialBuilder[E, Builder]{

      override def nextGeneration: Seq[Builder] =
        available.map(e => Builder(seq :+ e, available.filter(_ != e)))
    }

    val start = Builder(Vector(), arg)
    generateCombinatorials(start, arg.length).map(_.seq)
  }
}

まぁ、いくらかはスッキリしたかな？

Builder の nextGeneration メソッド
generateCombinatorials() メソッドに渡す引数

あたりを注意して見れば充分かと思います。

いくつかの応用

『Java によるアルゴリズム事典』には載ってませんが、上記の CombinatorialBuilder と generateCombinatorials を使うと簡単に実装できる順列の仲間があるので、簡単に見ていきましょう。

部分順列
順列（置換の符号を同時に計算する）
重複順列

部分順列

「n 個のモノから r 個選んで並べる」という、高校数学でよく出てくる部分順列（正式名称かどうか定かでない）を生成してみましょう。　上記で見てきた順列生成のアルゴリズムでは、generateCombinatorials() メソッドに渡す繰り返し回数（Int 型の第2引数）を arg.length ではなく r （選ぶ個数）にするだけで部分順列が生成できます。　後日見る予定の、『Java によるアルゴリズム事典』に載っている4つのアルゴリズムのうちの残り3つのものではこのようになりません。

ということで、コードは大体同じ。　r に相当する、選ぶ個数を指定する Int 値（ここでは名前を rank にしている）をメソッド引数に追加して、generateCombinatorials() メソッドに渡しているだけです：

object Permutation{

  def allPermutations[E](arg: Seq[E], rank: Int): Seq[Seq[E]] = {

    case class Builder(seq: Vector[E], available: Seq[E])
        extends CombinatorialBuilder[E, Builder]{

      override def nextGeneration: Seq[Builder] =
        available.map(e => Builder(seq :+ e, available.filter(_ != e)))
    }

    val start = Builder(Vector(), arg)
    generateCombinatorials(start, rank).map(_.seq)  // 回数が変更されているだけ
  }
}

使用コードはこんな感じ：

val pps = Permutation.allPermutations(0 until 3, 2)

assert(pps == Seq(
  Seq(0, 1), Seq(0, 2),
  Seq(1, 0), Seq(1, 2),
  Seq(2, 0), Seq(2, 1)))

置換の符号を同時に計算する

行列式を定義通り計算するときのように、全順列（置換）にわたって符号を使った計算をする場合、順列の生成と同時に符号も計算しておくとパフォーマンス的に安心。　ということで、ここでは符号も計算していくアルゴリズムを見ていきます。

まずは、順列生成のアルゴリズムの箇所で出てきた例を使って、符号の計算方法を見てみましょう。　6次の順列を生成しているときに現れるペア

(034, 125)

について、「使用可能な数字」をそのまま「構築中の順列」の末尾につけた 034125 は符号 +1 を持ちます。　さて、このペアに構築1ステップを施した場合、生成されたペアについて同じように計算した符号は

           / (0341, 25)  +1
(034, 125) - (0342, 15)  -1
           \ (0345, 12)  +1

となります。　つまり、上から順に正負が入れ替わります。　これは、次に使う数字を「使用可能な数字」の先頭へ移動するのに必要な互換の数を考えれば分かると思います。　このステップを繰り返すと、「使用可能な数字」の偶数番目（インデックスは奇数）を使うときには符号を変える、という計算を順列生成と一緒に行っていけばいいことがわかります。

では実装。　メソッド名は allPermutationsWithSign() としましょう。　順列（置換）の符号は数学的な計算でしか使わないかと思うので、このメソッドの引数は Seq ではなく次数 (degree) を表す Int とし、返り値は（どこかで定義されている）Permutation オブジェクトとします（まぁ、並べ替えられた Seq と符号の Int のタプルとかでもいいんですけど）：

trait Permutation

object Permutation{

  /** 符号を保持する Permutation オブジェクトを生成する */
  private def signed(suffices: Seq[Int], sign: Int): Permutation = ???

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

    case class Builder(suffices: Vector[Int], available: Seq[Int], sign: Int)  // 符号も保持
      extends CombinatorialBuilder[Int, Builder]{

      override def nextGeneration: Seq[Builder] =
        available.zipWithIndex.map{ case (e, i) =>  // インデックスも使うので zipWithIndex で。
          Builder(
            suffices :+ e,
            available.filter(_ != e),
            if(i % 2 == 0) sign else -sign)  // 符号の計算
        }

      def toPermutation: Permutation = signed(suffices, sign)
    }

    val start = Builder(Vector(), 0 until degree, 1)
    generateCombinatorials(start, degree).map(_.toPermutation)
  }
}

このアルゴリズムでは次数 (degree) が0の場合うまくいかないので、require() で除外しています。

重複順列

応用の最後は重複順列。　指定された要素を何回でも使っていい場合の順列です。　高校数学でもそうですが、普通の順列よりも重複順列の方が簡単。　「使用可能な数字」は常に同じなので、Builder に定義していた available プロパティが必要なくなります：

// Permutation コンパニオンオブジェクトとは別のオブジェクトに定義してます。
object WithRepetition{

  def allPermutations[E](seq: Seq[E], rank: Int): Seq[Seq[E]] = {

    case class Builder(seq: Vector[E])  // available 不要
      extends CombinatorialBuilder[E, Builder]{

      override def nextGeneration: Seq[Builder] =
        seq.map(e => Builder(suffices :+ e))
    }

    generateCombinatorials(Builder(Vector()), rank).map(_.seq)
  }
}

使い方は部分順列と同じです：

val ps = WithRepetition.allPermutations(0 until 3, 2)

asssert(ps == Seq(
  Seq(0, 0), Seq(0, 1), Seq(0, 2),
  Seq(1, 0), Seq(1, 1), Seq(1, 2),
  Seq(2, 0), Seq(2, 1), Seq(2, 2)))

まぁ特にどうってことはないですね。

重複順列と似たような順列の仲間として、「同じものを含む順列」というのがあります。　これは各要素について使用できる回数が定まっている（重複順列の場合は無限個とみなせる）順列です。　この「同じものを含む順列」も CombinatorialBuilder トレイトと generateCombinatorials() メソッドを使って実装できますが、今までのものに比べて少々複雑になるのでここでは取り上げません（言うほど複雑でもないですが）。

いろいろ脱線しましたが『Java によるアルゴリズム事典』に載っている4つの順列生成アルゴリズムの1つ目が終了。　次回は残りの3つをザッと見ていく予定。