Heapのアルゴリズム
異なるn要素の置換を考える。Heapはこれらの要素の各置換をそれぞれ1度だけ生成するために入れ替える要素のペアを選択する体系的方法を発見した。その方法を再帰的やりかたで説明しよう。まずカウンターiを0にセットする。そして以下のステップをiがnと等しくなるまで繰り返す。まず最後の要素と隣接する最初のn−1要素の置換(n−1)!個をアルゴリズムで生成する。これは最後の要素で終わる置換を全て生成する。次にnが奇数の場合最初の要素と最後の要素を入れ替え、nが偶数の場合はi番目の要素と最後の要素を入れ替える(最初のイテレーションではnの偶奇で違いはない)。iに1を加算し、最初に戻る。各イテレーションでこのアルゴリズムは「最後」の位置に移動した要素で終わる全置換を生成する。以下の疑似コードは長さnのデータ配列の全置換を出力する。
このアルゴリズムは非再帰的に書くこともできる。