Heapのアルゴリズム
Heapのアルゴリズムはn個のオブジェクトの全ての置換を生成するアルゴリズムである。1963年にB. R. Heapによって提案された。[1]このアルゴリズムは移動を最小化する。つまり、各置換は前の置換から1ペアを交換するだけで生成され、他のn−2要素を操作する必要はない。1977年の置換生成アルゴリズムの論評で、Robert Sedgewickはこのアルゴリズムをコンピュータによる現時点で最も効率的な置換生成用アルゴリズムと結論づけた。[2]
Heapのアルゴリズムによって生成されたn個のオブジェクトの置換列はn+1個のオブジェクトの置換列の最初になっている。したがってHeapのアルゴリズムは無限置換列を生成する(オンライン整数列大辞典の数列 A280318)。
概要
異なるn要素の置換を考える。Heapはこれらの要素の各置換をそれぞれ1度だけ生成するために入れ替える要素のペアを選択する体系的方法を発見した。その方法を再帰的やりかたで説明しよう。まずカウンターiを0にセットする。そして以下のステップをiがnと等しくなるまで繰り返す。まず最後の要素と隣接する最初のn−1要素の置換(n−1)!個をアルゴリズムで生成する。これは最後の要素で終わる置換を全て生成する。次にnが奇数の場合最初の要素と最後の要素を入れ替え、nが偶数の場合はi番目の要素と最後の要素を入れ替える(最初のイテレーションではnの偶奇で違いはない)。iに1を加算し、最初に戻る。各イテレーションでこのアルゴリズムは「最後」の位置に移動した要素で終わる全置換を生成する。以下の疑似コードは長さnのデータ配列の全置換を出力する。
procedure generate(n : integer, A : array of any): if n = 1 then output(A) else for i := 0; i < n; i += 1 do generate(n - 1, A) if n is even then swap(A[i], A[n-1]) else swap(A[0], A[n-1]) end if end for end ifこのアルゴリズムは非再帰的に書くこともできる。[3]
procedure generate(n : integer, A : array of any): c : array of int for i := 0; i < n; i += 1 do c[i] := 0 end for output(A) i := 0; while i < n do if c[i] < i then if i is even then swap(A[0], A[i]) else swap(A[c[i]], A[i]) end if output(A) c[i] += 1 i := 0 else c[i] := 0 i += 1 end if end while関連項目
- Steinhaus–Johnson–Trotter algorithm