次の順列 - 倭算数理研究所

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。　以前に置換のアルゴリズムを扱ったときに、『Java によるアルゴリズム事典』に「置換の生成」がなくておかしいなぁと思ってたら、「順列」「順列の生成」の項目にあることを発見。　それくらい気付よ、自分w

ということで「置換の生成」についてやり直そうと思いますが、まずはその他の順列に関する項目を見ていきます。　今回は定められた次数の順列に対して、辞書順序で並べた場合の次の順列を生成するアルゴリズムを見ていきます。　辞書順序 (lexicographic order) は、ここでは既知とします（とか言いつつ、次回やるかも）。

この記事では ${ n }$ 個のモノの順列（ ${ n }$ 次の順列）は0から ${ n-1 }$ （1から ${ n }$ ではなく）の置換とし、

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

を、上の整数が昇順に並んでいるとして、下の数字を取り出して [035421] と書くことにします。

アルゴリズム

まずはアルゴリズムの概要を見ていきましょう。　1次の順列は [0] 1つしかないので次の順列はありません。　以降は2次以上の順列を考えます。　 ${ n }$ 次の順列で辞書順序的に最後のものは [(n-1)(n-2)…210] で、この記法での隣接する整数の大小関係に着目すると

　　 ${ \displaystyle\begin{align*} n-1 > n-2 > \cdots > 2 > 1 > 0 \end{align*}}$

のように降順に並んでいます。　これを踏まえて、次の順列を取得する方法は

隣接する整数間の大小関係が「<」になっている一番最後の箇所（左側の整数の位置を i、そこにある整数を a とする）を検索する
a より大きい整数で一番最後にある整数の箇所 j を検索する
この2つの整数を交換する
最初の整数があった箇所より末尾を反転する

となります。　まぁ、文章で説明しても分かりにくいので具体例を見ていきましょう。　6次の順列 [035421] に対して上記の手順を施すと、

順序が昇順になっているのは 3 < 5 の箇所（左側の整数の位置 i = 1、値 a = 3）
a より大きい一番最後の整数は4 （位置 j = 3）
i と j の位置の整数を交換する [045321]
i より末尾（i は含まない）を反転する [041235]

となって、次の順列が得られます。　i より末尾（i を含まない）は降順になっているので、j にある整数は i より末尾にある中で i の次に大きい整数です。　よって、i と j の位置の整数の交換後でも、元の i の位置より末尾の部分は降順になっています。　次のステップでこの部分を反転すると、ここが昇順になります。　要は、i の位置の整数を適当な次の整数に大きくして、それより末尾を昇順にリセットしています（【修正】一部、説明が間違っていたので修正しました）。　これで辞書順序的に次の順列が得られます。

実装

では、上記の手順を実装してみましょう。　そのまえにちょっと準備。

準備

Scala の Seq トレイトで要素の位置を交換する swap のようなメソッドが見当たらなかったので別途定義しておきます：

  def swap[E](seq: Seq[E], i: Int, j: Int): Seq[E] =
    if(i == j) seq
    else{
      seq.indices.map {
        case x if x == i => seq(j)
        case x if x == j => seq(i)
        case x => seq(x)
      }
    }

まぁ、実装はともかく使い方は簡単：

val seq = Seq("a", "b", "c", "d")
val swapped = swap(seq, 1, 3)
assert(swapped == Seq("a", "d", "c", "b"))

他は Scala のコレクションに定義されているメソッドで事足りますが、sliding(Int) はちょっと説明が要りますかね。　いや、説明より返り値を書いとく方が分かりやすいかな：

assert(
  Seq("a", "b", "c", "d").sliding(2).toSeq ==
    Seq(Seq("a", "b"), Seq("b", "c"), Seq("c", "d")) )

i 番目の要素は、i から始まって2個（sliding() メソッドの引数）の Seq です。　要素の被りがあるので注意。　もし被らないようにしたいなら grouped() メソッドを使います。　sliding() メソッドで返されるのは Iterator オブジェクトなので、toSeq によって Seq に変換しています。

他のメソッドはメソッド名で想像がつくかと思います。　正式には Scaladoc など参照。

next メソッド

さて、以上を踏まえて次の順列を取得するメソッドを実装しましょう。　このメソッドは next メソッドとし、返り値は Option[Permutation] とします。　次の順列がない場合は None を返します*1。

next メソッドは Permutation クラスに定義します。　Permutation クラスには Seq[Int] を返す suffices メソッドを定義してますが、これは上記の表記での [035421] を Seq[Int] として返します。

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

  /** 次数 */
  def degree: Int = suffices.length

  /** 通常の順列の記法で、上の整数を与えたときに下の整数を返す */
  def apply(i: Int): Int = suffices(i)

  def next: Option[Permutation] = degree match {
    case 1 => None  // 1つの順列は this １つだけ
    case _ =>
      suffices.sliding(2).toSeq.lastIndexWhere(p => p(0) < p(1)) match {
        case -1 => None  // this が辞書順序的に最後の要素
        case i =>  //  suffices が Seq(0, 3, 5, 4, 2, 1) の場合
          // i = 1 (∵ 3 < 5)
          val a = apply(i)  // a = 3
          val j = suffices.lastIndexWhere(p => a < p)  // j = 3 (∵ 3 < 4)
          val swapped = swap(suffices, i, j)  // swapped = Seq(0, 4, 5, 3, 2, 1)

          val (first, second) = swapped.splitAt(i+1)
            // first = Seq(0, 4), second = Seq(5, 3, 2, 1)
          val newSuffices = first ++ second.reverse  // newSuffices = Seq(0, 4, 1, 2, 3, 5)
          Some(new Permutation(newSuffices))
      }
  }
}

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

処理内容は上記の手順そのままです。　むしろコード見た方が分かりやすいかな？　特にコレクションなどは、（一般的に使われてる、他の言語でも使われているような）述語となるメソッドが豊富にあるとコードが何をやってるのか分かりやすくて、書く人にも読む人にも優しい（易しい）。　正直、『Java によるアルゴリズム事典』のコード見ても何やってるのか理解するのに結構時間と労力が必要だった。　まぁ、その分実行時のパフォーマンスはいいんだろうけど。

このコードの使い方は、まぁ特に難しくありません。　Permutation(1, 0, 2) で [102] の順列を生成します：

assert( Permutation(0).next == None )

assert( Permutation(0, 1).next == Some(Pemutation(1, 0)) )
assert( Permutation(1, 0).next == None )

assert( Permutation(0, 3, 5, 4, 2, 1).next == Some(Permutation(0, 4, 1, 2, 3, 5)) )