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

データ構造とアルゴリズム Advent Calendar 2019の1日目の記事です。 2日目は@yurahunaさんによる「三角形分割の数え上げとランダムサンプリング」です。 6月にグレッグ・イーガン氏のHPで見つけた順列生成アルゴリズムについてブログを書きました。 そのあとに元ネタの論文1を読んでいたのですが、おもしろい順列生成アルゴリズムを含んでいたのでGoでライブラリ化してみました。 deltam/perm: Permutation generator based on group theory written in Go 自分のベンチマークでは再帰関数で実装したナイーブなアルゴリズムより33％ほど早いですが、高速さが売りというよりも「順列への最小限の操作セットのみを駆使して順列生成できないか？」という研究の流れから出てきた副産物的なアルゴリズムです。 ただその最小限の操作セットを