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