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を繰り返し適用した系列はすべての順列が一回だけ登場するものになっています。
