2つの操作のみで全順列を列挙する：対称群のグラフ上のハミルトン路にもとづく順列生成の紹介と実装

データ構造とアルゴリズム Advent Calendar 2019の1日目の記事です。
2日目は@yurahunaさんによる「三角形分割の数え上げとランダムサンプリング」です。

6月にグレッグ・イーガン氏のHPで見つけた順列生成アルゴリズムについてブログを書きました。
そのあとに元ネタの論文¹を読んでいたのですが、おもしろい順列生成アルゴリズムを含んでいたのでGoでライブラリ化してみました。

deltam/perm: Permutation generator based on group theory written in Go

自分のベンチマークでは再帰関数で実装したナイーブなアルゴリズムより33％ほど早いですが、高速さが売りというよりも「順列への最小限の操作セットのみを駆使して順列生成できないか？」という研究の流れから出てきた副産物的なアルゴリズムです。

ただその最小限の操作セットを駆使するアイデアが面白く、最終的に出来るルールが非常にシンプルで実装も短くできるのでアドベントカレンダーに乗じて紹介しようと思います。

まずアルゴリズムの背景となる論文の内容を紹介し、その結果をルール化して順列生成のプログラムを作ります。

グレッグ・イーガン経由で知った順列生成アルゴリズム

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を適用する。

1. 左端の数字がnではない。
2. 順列中のnの右隣の数字をrとする（nが右端なら左から2番めをrとする）。左端の数字をfとし、r が 1+(f-2) mod (n-1) と等しい。
3. 現在の順列が(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を繰り返し適用した系列はすべての順列が一回だけ登場するものになっています。

実験