Heapのアルゴリズム

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[0], 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[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

関連項目

脚注 

置換
アルゴリズム