Heapのアルゴリズム

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