Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は前回に引き続き、全順列を生成するアルゴリズムを見ていきます。 全開は『Java によるアルゴリズム事典』に載っている4つのアルゴリズムのうち1つ目のものを見ましたが、今回は残りの3つをやります。
この記事では n 個のモノの順列（置換）を n 次の順列（置換）と呼び、0から n-1 の数字の並び（1から n ではなく）で表すことにします。
アルゴリズムその2、その3では、前回導入したCombinatorialBuilder トレイト、generateCombinatorials() メソッドを使います。 内容については前回を参照。
この記事の内容
参考
アルゴリズム その2
アルゴリズムその2では、n 次の順列を構築するために0から n-1 までの数字を順次付加していきます。 例えば、0から2の数字の並び 102 があるとき、ここに以下の ^ の位置に3を挿入していきます：1 0 2 ^ ^ ^ ^
樹形図で描くと以下の様になります：
/ 1023
/ 1032
102
\ 1302
\ 3102上から順に見ていくと、3が段々前へ行く感じです。 後ろから順に入れているのは、生成される順列の最初の要素が昇順に並ぶようにするためです。
実際に3次の順列を全て生成してみましょう。 最初は要素がないので としておきましょう:を追加して4次の順列を4つ構築します：
/ 012
01 - 021
/ \ 201
φ - 0
\ / 102
10 - 120
\ 210生成された順列は辞書順序にはなっていません。 前回のアルゴリズムその1とは逆に、世代が重なるほど分岐が多くなっていきますね。 遅延評価だとこちらの方がメモリの使用量が少なそうな気がします（測ってない）。
実装
では実装。 まず、あまり本質ではない処理「Vector[E] 型の vec の位置 i に要素 e を追加する」メソッド insertAt[E](vec: Vector[E], i: Int, e: E) を定義しておきます：def insertAt[E](vec: Vector[E], i: Int, e: E): Vector[E] = i match { case 0 => e +: vec case _ if i == vec.length => seq :+ e case _ => val (first, second) = vec.splitAt(i) first ++: e +: second }
これを踏まえて、アルゴリズムその2での順列生成を行うコードを書いてみましょう。 メソッド名はallPermutations2() とします。 ここではアルゴリズムその1のように Seq[E] を受け取って置換された Seq[E] の Seq を返すのではなく、生成したい順列の次数を受け取って置換を表す Seq[Int] の Seq を返すとします。 これは特に制限があるからというわけではなく、次のステップで追加する要素（整数）が簡単に分かるのでコードも簡潔になるからというだけです。 任意の Seq[E] を受け取って置換するコードも、少し改良すれば問題なく書けます：
object Permutation{ def allPermutations2(degree: Int): Seq[Seq[Int]] = { // degree は順列の次数 require(degree >= 0) case class Builder(seq: Vector[Int], n) // n は seq.length と等しい extends CombinatorialBuilder[Int, Builder]{ override def nextGeneration: Seq[Builder] = (n to 0 by -1).map(i => Builder(insertAt(seq, i, n), n+1)) // 0から n の位置まで（逆順に）数字 n を挿入 } val start = Builder(Vector(), 0) generateCombinatorials(start, degree).map(_.seq) // degree 回繰り返す } }
Builder クラスに n をプロパティとして持たせてますが、これは seq.length に等しいので定義しなくてもコードは書けます。 このコードは degree が0以上で動きます。 degree が0の場合は空集合を要素に持つ Seq が返されます（Seq(Vector())）。
上記のコードは以下の様に実行できます：
val ps = Permutation.allPermutations2(3) assert(ps == Seq( Seq(0, 1, 2), Seq(0, 2, 1), Seq(2, 0, 1), Seq(1, 0, 2), Seq(1, 2, 0), Seq(2, 1, 0)))
アルゴリズム その3
アルゴリズムその3は互換（2つの要素の置換）を繰り返して全順列を生成するアルゴリズムです。 置換の生成手順は、要素の並びに対してまず1つの位置を固定し、その位置もしくはそれより前の位置について互換を施し、その結果に対して固定する位置を前にずらして同様の手順を繰り返します。 固定する位置は要素の並びの最後から始めます。この手順の1ステップを樹形図で描くと以下の様になります。 ペア (,) の左側は並び替える要素（数字）の並び、右側は固定する位置（0から始まる）です：
/ (015432, 2)
^
/ (014532, 2)
(015432, 3) ^^
^ \ (045132, 2)
^ ^
\ (415032, 2)
^ ^右側のペアで ^ が付いている場所が互換を施されたところです。 ^ が1つしかない場合は自分自身との互換、つまり変換していません。
実際に3次の順列を全て生成してみると以下の様になります：
/ (012, 0)
(012, 1)
/ \ (102, 0)
/ (021, 0)
(012, 2) - (021, 1)
\ (201, 0)
\ / (210, 0)
(210, 1)
\ (120, 0)実装
では実装。 まず、本質とはあまり関係ない「Vector[E] 型の vec の位置 i と j の要素を入れ替える」メソッド swap[E](vec: Vector[E], i: Int, j: Int) を定義しておきます：def swap[E](vec: Vector[E], i: Int, j: Int): Vector[E] = if(i == j) vec else{ val e = vec(i) vec.updated(i, vec(j)).updated(j, e) }
さて本題。 アルゴリズムその3で全順列を生成するメソッドを allPermutations3() として実装しましょう。 このメソッドはアルゴリズムその1のメソッド allPermutations() と同じように、引数として Seq[E] 型のオブジェクトをとるようにします。
object Permutation{ def allPermutations3[E](arg: Seq[E]): Seq[Seq[E]] = { case class Builder(seq: Vector[E], n: Int) // n は入れ替え位置の固定された方 extends CombinatorialBuilder[E, Builder]{ override def nextGeneration: Seq[Builder] = (n to 0 by -1).map(i => Builder(swap(seq, i, n), n-1)) // i は入れ替え位置のもう一方の方 } val start = Builder(arg.toVector, arg.length-1) generateCombinatorials(start, arg.length).map(_.seq) } }
まぁ大して難しくないですね。
上記のコードは以下の様に実行できます：
val n = 3 val ps = Permutation.allPermutations3(0 until n) assert(ps == Seq( Seq(0, 1, 2), Seq(1, 0, 2), Seq(0, 2, 1), Seq(2, 0, 1), Seq(2, 1, 0), Seq(1, 2, 0)))
アルゴリズム その4
最後のアルゴリズムその4は階乗進数をカウンター（以下、階乗カウンター）として用いる方法です。 ただし、以前の記事で行った階乗進数から置換へ変換するアルゴリズムとは異なるので、生成される置換は辞書順序には並んでいません。 このアルゴリズムは文章での説明が面倒そう（というかこの方法で全順列が生成されることをいまいち理解していない）なので、実装を元に見ていきます。このアルゴリズムでは、「階乗カウンターの管理」と「その階乗カウンターによる次の置換の生成」からなります。 『Java によるアルゴリズム事典』ではまとめて書いてありますが、ここではデバッグを簡単にするため、この2つをちょっと分離して見ていきます。 コード的には少々長くなりますが。
まずは階乗カウンターを管理するコード。 階乗カウンター FactorialCounter は、階乗進数の各桁の数字を保持する Seq[Int] 型の c と、（おおまかに言って）カウントダウンによって数字を減らした階乗進数の桁を保持する Int 型の k からなります。 ちなみに、階乗カウンターは状態を持たずに、カウントダウンは next メソッドによって新たに FactorialCounter オブジェクトを生成することで行うようにしています。 関数型プログラミングが目的だからね。 実装するとこんな感じ：
case class FactorialCounter(c: Seq[Int], k: Int){ def hasNext: Boolean = k != -1 def next: FactorialCounter = c.indexWhere(_ != 0) match { case -1 => FactorialCounter(Nil, -1) // c の要素が全て 0 になったら終わり case newK => val s = c.slice(newK, c.length) val newC = (0 until newK) ++: (s.head-1) +: s.tail FactorialCounter(newC, newK) } } def factorialCounters(degree: Int): Seq[FactorialCounter] = { val start = FactorialCounter(0 until degree, 1) Stream.iterate(start)(_.next).takeWhile(_.hasNext) }
『Java によるアルゴリズム事典』とは少々変えているところがありますが、大事なのは factorialCounters() メソッドがどのような要素からなるのかです。 次数が3の場合に FactorialCounter のプロパティ c, k の値を見てみると以下の様になります：
c k ------------ (0, 1, 2), 1 (0, 0, 2), 1 (0, 1, 1), 2 (0, 0, 1), 1 (0, 1, 0), 2 (0, 0, 0), 1
c は から始めて1ずつ値を減らしていきます（桁の並びが逆になっています）。 c は階乗進数の各桁の数字を桁の小さいものから保持しますが、0! の桁の数字0を常に持たせています。 これを取り除いて省メモリ化もできなくないですが、この後の次の置換の生成コードも変わってきます。
次は、この階乗カウンターを使って次の置換を生成するコードです。 いろいろ周辺コードが書かれてますが、本質は swap() による要素の入れ替えです。 swap() メソッドはアルゴリズムその3に出てきたものと同じです。
このアルゴリズムでは generateCombinatorials() が使えないので、遅延評価のために Stream#iterate() メソッドを使っています。 階乗カウンターの各オブジェクトは前の置換から次の置換を生成する「変換」に対応するので、n! 個の階乗カウンターから iterate() メソッドで Seq を生成すると、最初の要素を含めて n! + 1 個の要素ができてしまいます。 幸い、常に階乗カウンターの最初のオブジェクトが恒等変換に対応するようになっているようなので、最初のオブジェクトを drop(1) で落としています。
object Permutation{ def allPermutations4[E](arg: Seq[E]): Seq[Seq[E]] = { val counters = factorialCounters(arg.length).drop(1) // 最初 のカウンターは恒等変換となるので除去 Stream.iterate((arg, counters)){ // Seq[E] と Seq[FactorialCounter] のタプルで iterate case (a, Nil) => (Nil, Nil) // Seq[E] を Nil にして最後だというマーキング case (a, fcs) => val FactorialCounter(c, k) = fcs.head val i = if(k % 2 == 0) 0 else c(k) // この i と次行の swap が次の置換を生成する本質コード (swap(a, i, k), fcs.tail) }.takeWhile(_._1.nonEmpty) // Seq[E] が Nil になるまで続ける .map(_._1) // Seq[E] と Seq[FactorialCounter] のタプルから Seq[E] を抜き出す } }
これを実行すると以下の様になります：
val n = 3 val ps = Permutation.allPermutation4(0 until n) assert(ps ==Seq( Seq(0, 1, 2), Seq(1, 0, 2), Seq(2, 0, 1), Seq(0, 2, 1), Seq(1, 2, 0), Seq(2, 1, 0)))
まぁ、もうちょっと実装コードを簡単にすることはできるかも知れませんが、あまり深入りしてもしょうがなさそうなアルゴリズムなのでこの辺でお開きに。
次回は順列に変わって組合せ関連のコードをやる予定。
- 作者: 奥村晴彦,杉浦方紀,津留和生,首藤一幸,土村展之
- 出版社/メーカー: 技術評論社
- 発売日: 2003/05
- メディア: 単行本
- 購入: 2人 クリック: 61回
- この商品を含むブログ (60件) を見る
