Heapのアルゴリズム

「ヒープソート」とは異なります。

Heapのアルゴリズムは、n個のオブジェクトの全ての置換を生成するアルゴリズムである。1963年にB. R. Heapによって提案された^[1]。このアルゴリズムは移動を最小化する。つまり、各置換は前の置換から1ペアを交換するだけで生成され、他のn−2要素を操作する必要はない。1977年の置換生成アルゴリズムの論評で、Robert Sedgewickはこのアルゴリズムをコンピュータによる現時点で最も効率的な置換生成用アルゴリズムと結論づけた^[2]。

HeapのアルゴリズムをA (琥珀色)、B (青色)、C (シアン)、D (ダークレッド)の4文字に使ってできる24の置換と23のスワップの図

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