サムネイル|720x720ピクセル|HeapのアルゴリズムをA (琥珀色)、B (青色)、C (シアン)、D (ダークレッド)の4文字に使ってできる24の置換と23のスワップの図
Heapのアルゴリズムは、個のオブジェクトの全ての置換を生成するアルゴリズムである。1963年にB. R. Heapによって提案された。このアルゴリズムは移動を最小化する。つまり、各置換は前の置換から1ペアを交換するだけで生成され、他の要素を操作する必要はない。1977年の置換生成アルゴリズムの論評で、Robert Sedgewickはこのアルゴリズムをコンピュータによる現時点で最も効率的な置換生成用アルゴリズムと結論づけた。
Heapのアルゴリズムによって生成された個のオブジェクトの置換列は個のオブジェクトの置換列の最初になっている。したがってHeapのアルゴリズムは無限置換列を生成する()。
概要 異なる要素の置換を考える。Heapはこれらの要素の各置換をそれぞれ1度だけ生成するために入れ替える要素のペアを選択する体系的方法を発見した。その方法を再帰的やりかたで説明しよう。まずカウンターを0にセットする。そして以下のステップをがと等しくなるまで繰り返す。まず最後の要素と隣接する最初の要素の置換個をアルゴリズムで生成する。これは最後の要素で終わる置換を全て生成する。次にが奇数の場合最初の要素と最後の要素を入れ替え、が偶数の場合は番目の要素と最後の要素を入れ替える(最初のイテレーションではの偶奇で違いはない)。に1を加算し、最初に戻る。各イテレーションでこのアルゴリズムは「最後」の位置に移動した要素で終わる全置換を生成する。以下の疑似コードは長さのデータ配列の全置換を出力する。
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, A[n-1]) end if end for end if
このアルゴリズムは非再帰的に書くこともできる。
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, 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
脚注
関連項目