順列を生成する

algorithm .groovy

まずは Groovy の機能で

Groovy の List は順列を生成するメソッドを持っている。*1

[1,2,3].permutations().each { println it }

ただし、辞書式順序ではない。

[1, 2, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
[2, 1, 3]
[1, 3, 2]


でも Collection#eachPermutation は辞書式順序だ。

[1,2,3].eachPermutation { println it }

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]


どちらも、内部では PermutationGenerator を呼び出している。
permutations は結果を HashSet で返しているため、生成したときの順序が失われたようだ。*2

new PermutationGenerator([1,2,3]).each { println it }


PermutationGenerator は、Michael Gilleland 氏が 『Discrete Mathematics and Its Applications, 2nd edition』 を参考に Java で記述したものを、Groovy に取り込んだらしい。
Michael Gilleland 氏のサイトへのリンク：


Groovy で eachPermutation 風に書き直してみる。*3

def perm(a, callback) {
  // 生成する順列の総数を求める
  def total = a.inject(1) { acc, val -> acc * val }
  total.times {
    if (it != 0) {
      // a を末尾からたどって最初に昇順になる位置 j を探す
      def j = a.size() - 2
      while (a[j] > a[j+1]) j--
      // a[j+1] 以降は降順なので末尾からたどって最初に a[j] を越える値を探す
      def k = a.size() - 1
      while (a[j] > a[k]) k--
      // a[j] と a[k] を入れ替える
      Collections.swap(a, j, k)
      // a[j+1] 以降を反転させる
      Collections.reverse(a.subList(j+1, a.size()))
    }
    callback(a)
  }
}
 
perm([1,2,3]) { println it }

コメントを訳したが手順が書かれているだけで意味が分からない。
考えてみたら降順の範囲は順列を生成し終えたので次の桁を1つ進めるだけだった。

他のアルゴリズムを Groovy で書いてみる

河西朝雄 氏の 『C言語によるはじめてのアルゴリズム入門』 から
def perm(a, callback) {
  def n = a.size()
  def rec = { i ->
    if (i < n)
      for (j in i..<n) {
        Collections.rotate(a.subList(i, j+1), 1)
        call(i+1)
        Collections.rotate(a.subList(i, j+1), -1)
      }
    else
      callback(a)
  }
  rec(0)
}

perm([1,2,3]) { println it }

Collections の rotate が使えるので少しシンプルになる。
ポイントをまとめると

  • for と rotate の組合せはすべての要素を順に先頭にするための処理である
    • このとき先頭にした要素以外は元の順序を維持する
  • 再帰で先頭以外の要素も同様に処理する
奥村晴彦 氏の 『C言語による最新アルゴリズム辞典』 から
def perm(a, callback) {
  def n   = a.size()
  def ok  = new boolean[n]
  def p   = []
  def put = { pos, k ->
    ok[k]  = false
    p[pos] = a[k]
    if (pos < n-1)
      for (i in 0..<n) {
        if (ok[i]) call(pos+1, i)
      }
    else
      callback(p)
    ok[k] = true
  }
  Arrays.fill(ok, true)
  for (i in 0..<n) put(0, i)
}

perm([1,2,3]) { println it }

要素を1つ選んで先頭に置き残りの要素を再帰的に処理するので rotate と同じだ。
違うところ

  • rotate で回して戻すのではなく ok で配置した要素を管理している
  • 引数は変更しない


階乗進法を使うものが載っていたが辞書式順ではないものでかつ利点が分からない。
階乗進法と順列で検索したら利点が書かれていた： http://www004.upp.so-net.ne.jp/s_honma/urawaza/permutation.htm
辞書式順序で i 番目の順列だけ取得できることみたいだ。
とりあえず実装してみる。*4

def factrep(n, size) {
  def a    = []
  def fact = (1..size).inject([1]) { acc, val -> acc << acc.last() * val }
  size.downto(1) { i ->
    a << n.intdiv(fact[i])
    n %= fact[i]
  }
  a << 0
}

def perm(a, i, callback) {
  def n = a.size()
  def c = factrep(i, n-1)
  def p = c.collect { a.remove(it) }
  callback(p)
}

def perm(a, callback) {
  def n     = a.size()
  def total = (1..n).inject(1) { acc, val -> acc * val }
  for (i in 0..<total) {
    perm(a.clone(), i, callback)
  }
}

perm([1,2,3]) { println it }
perm([1,2,3], 3) { println it } // [2, 3, 1]

まとめ

辞書式順序で順列を生成する方法

  • 末尾から順列を生成し終わった位置を探す方法
  • 先頭から順に要素を配置する方法
  • 階乗進法を使って i 番目の順列を得る方法

*1:組合せを生成するメソッドは持っていない。Collection#combinations はデカルト積を生成する。

*2:LinkedHashSet なら順序は保持されていた。

*3:a はインデックスで実際はその並びの items を返している。

*4:i ｗインデックスにしたので i+1 番目になる。