SF作家のグレッグ・イーガンさんは最小超置換文字列の分散探索プロジェクトを主催しています。それ自体も興味深いんですが、解説ページで紹介されていた副産物の順列を列挙するアルゴリズムが面白かったので紹介＆実装してみます。
（Local Ruleのセクションで解説されている内容の紹介です。）
（追記：順列生成アルゴリズムをライブラリ化しました deltam/perm: Permutation generator based on group theory written in Go.）
順列生成アルゴリズム
まず順列の順番を入れ替える写像sigma、deltaを次のように定義します。
sigma: (2,3,4,...,n-1,n,1)
delta: (3,4,5,...,n-1,n,2,1)
始点の順列を(n-2, n-3, ..., 3, 2, n, 1)として、それに対して次のルールAを繰り返し適用します。
ルールA
以下の条件をすべて満たすなら現在の順列にdeltaを適用し、そうでないならsigmaを適用する。
- 左端の数字がnではない。
- 順列中のnの右隣の数字をrとする（nが右端なら左から2番めをrとする）。左端の数字をfとし、r が 1+(f-2) mod (n-1) と等しい。
- 現在の順列が
(1, n, n-1, ..., 3, 2)ではない。
（2番めの条件が分かりにくいので具体例を挙げると、順列(3, 1, 2, 4) ならf=3かつr=1で、1+(3-2) mod (4-1) = 1+1 = 2なので r = 1 ≠ 2となります）
始点からルールAを繰り返し適用した系列はすべての順列が一回だけ登場するものになっています。
実験
n=3の順列で実験してみます。まず始点は(2,3,1)です。
(2,3,1) : ルールA 1.OK 2.OK 3.OK -> delta
(1,3,2) : ルールA 1.OK 2.OK 3.NG -> sigma
(3,2,1) : ルールA 1.NG -> sigma
(2,1,3) : ルールA 1.OK 2.OK 3.OK -> delta
(3,1,2) : ルールA 1.NG -> sigma
(1,2,3) : 終了
全順列が出てきました。
4以上だと手計算が面倒なのでGoで書いてみました。
https://play.golang.org/p/hjt_iTAJWPo
$ go run perm_gen.go |head
[3 2 4 1]
[2 4 1 3]
[1 3 4 2]
[3 4 2 1]
[2 1 4 3]
[1 4 3 2]
[4 3 2 1]
[3 2 1 4]
[1 4 2 3]
[4 2 3 1]
$ go run perm_gen.go | wc -l
24
$ go run perm_gen.go |sort|uniq|wc -l
24
うまくいってますね。(4,3,2,5,1)から始めると5の全順列120個が出てくるので適当に書き換えて試してみてください。
イーガン先生が書いたJavaScriptによる実装も解説ページにリンクがあります（Supermutate.jsというやつ）。ページトップの文字がぐるぐる動いているのはそれで文字の全順列を表示しているみたいです。
なぜうまくいくのか？
グレッグ・イーガン先生は最小超置換の長さの上界を証明するためにAaron Williams氏の論文の結果を使っています。
この論文では順列と2つの写像による群をケイリーグラフというグラフ構造に変換したものの上に、ハミルトン路を構成しそれが必ず存在するということを証明しています。
ハミルトン路とはグラフのすべての頂点をそれぞれ一回だけ通る経路のことです（終点→始点にならない場合もある）。頂点＝順列なのでそのような経路を生成するアルゴリズムは順列生成アルゴリズムになります。上で紹介したアルゴリズムはイーガン先生が論文から少しアレンジしたものです。
上記の論文ではハミルトン路の存在以外にも次のことが証明されています。
- 論文が対象としているケイリーグラフにはちょうど2つのサイクルカバーが存在し、すべての頂点はそのどちらか一方に含まれる
- サイクルカバーを生成するアルゴリズムが存在する
サイクルカバーとはグラフ上の各頂点を一回だけ通るループのことです（すべての頂点を巡るものはハミルトンサイクルと呼ばれる）。この順列生成アルゴリズムはまず片方のサイクルカバーを生成し、始点に戻る直前の頂点でもう一方のサイクルカバーに移動して全頂点をめぐります。
サイクルカバーの次の頂点を生成するためのルールがルールAの1.2.です。3.は最初のサイクルカバーの終点を判別し、もう一方のサイクルカバーに移動するためのルールです。
普通の順列生成なら(1,2,3)から始めたいところですが、サイクルの終点を明確にするために(2,3,1)から始めてるんですね。ルールAを調整すれば(1,2,3)を始点に出来るかもしれないですが、出力するときに変換をかますほうが楽かも。
ケイリーグラフ上のハミルトン路の存在証明は上記の論文が初めてではないようですが、すでに知られているものよりかなりシンプルになったそうです。Goで書いたものも70行ほどなので素晴らしいですね。
（追記：今まで知られていたのは逆方向の移動を許すものや全数探索で見つけたもので、すべての n について構成法はこれが初めてのようです）
最小超置換との関わり
元論文ではdeltaは先頭二文字を入れ替える(2,1,3,4,...,n-1,n)写像になっています。イーガン先生がさらに二文字を後ろに持っていくようにしたのは超置換文字列を作るためです。
超置換はnの順列がすべて部分列として含まれる文字列のことです。sigma、deltaで順列を変換すると前の順列と先頭n-1、n-2文字が共通になります。変換するごとに1,2文字を追加していけばそれは超置換文字列になります。
上記のGoプログラムのmainをこんなふうに書き換えれば超置換を出力します。
func main() {
p := []int{2, 3, 1}
for i := 0; i < len(p); i++ {
fmt.Print(p[i])
}
add := 0
for i := 0; i < 6-1; i++ {
if ruleCheck(p) {
delta(p)
add = 1
} else {
sigma(p)
add = 2
}
for i := len(p) - add - 1; i < len(p); i++ {
fmt.Print(p[i])
}
}
}
// Output: 2313232121312123
この方法で作った超置換は部分列に重複が多く、残念ながら最小にはなりません。n=3の最小超置換は123121321です。
ただしこれによって数学的に証明された超置換を生成するアルゴリズムを作ることができて、超置換の長さの上界を示すことができます。
最小超置換問題の全体的な説明はこちらの記事が参考になります。イーガン先生の貢献も解説されています。
ハルヒ問題（最小超置換問題）の紹介 - Qiita
（おまけ）イーガン先生による最小超置換の分散探索プロジェクト紹介
Distributed Chaffin Method Results
いまアマチュア数学者業界で最小超置換が熱い！ 単純な予想を覆す複雑さを持ち、なんか新発見できるんではという希望があります。
イーガン先生は現在n=6の超置換を全探索してすでに知られたものが本当に最小か追試しています。
最小超置換の探索アルゴリズムのChaffin Method（これも考え方が興味深いので解説書きたい）を複数台のコンピュータで実行できるようにしたのがDistributed Chaffin Methodです。サーバもクライアントもイーガン先生が書いてます。
superperm/DistributedChaffinMethod at master · superpermutators/superperm
クライアントはCとJavaのものがあります。チーム名を決めて実行するとプロジェクトページに実績が載るので誘い合わせて参加するといいかも（私はぼっちチームですが…）。
現在のところ最小超置換を見つけることの実用的意味はまったくありませんが、すこしでも面白そうと思ったならクライアントを動かしてみませんか？
イーガン先生の熱情がどこから来るのか不明ですが、このような著作があるのと関係あるのかもしれません。（もしくは短編『ルミナス』のように数論の＜不備＞を発見しようとしているのかも？）
コード全体
// permutation generator
// author @deltam
package main
import "fmt"
func main() {
p := []int{3, 2, 4, 1}
for i := 0; i < 24; i++ {
fmt.Println(p)
if ruleCheck(p) {
delta(p)
} else {
sigma(p)
}
}
}
// 2 3 4 ... n-1 n 1
func sigma(p []int) {
n := len(p)
f := p[0]
copy(p[0:n-1], p[1:n])
p[n-1] = f
}
// 3 4 5 ... n-1 n 2 1
func delta(p []int) {
n := len(p)
f0 := p[0]
f1 := p[1]
copy(p[0:n-2], p[2:n])
p[n-2] = f1
p[n-1] = f0
}
func ruleCheck(p []int) bool {
n := len(p)
// 1.
if p[0] == n {
return false
}
pos := 0
for i := 0; i < n; i++ {
if p[i] == n {
pos = i
break
}
}
pos++
if pos == n {
pos = 1
}
// 2.
if p[pos] != 1+(p[0]-2+n-1)%(n-1) {
return false
}
// 3.
for i := 0; i < n; i++ {
if p[(i+1)%n] != n-i {
return true
}
}
return false
}
おわり。
（訂正 2019-06-30：ハミルトンサイクルとサイクルカバーの用語の意味を取り違えてたので修正）
0 件のコメント:
コメントを投稿