ヒープのアルゴリズム

Heap’s_algorithm

ヒープソート
と混同しないでくださいヒープのアルゴリズムは、n個のオブジェクトのすべての可能な順列を生成します。これは、1963年にBRヒープによって最初に提案されました。アルゴリズムは、動きを最小限に抑えます。要素の1つのペアを交換することにより、前の順列から各順列を生成します。他のn -2要素は妨害されません。1977年の順列生成アルゴリズムのレビューで、Robert Sedgewickは、当時、コンピューターによって順列を生成するための最も効果的なアルゴリズムであると結論付けました。
A（琥珀色）、B（青）、C（シアン）、D（濃い赤）の4文字を並べ替えるHeapのアルゴリズムで使用される24の並べ替えと23のスワップのマップ
長さのすべての順列のホイール図n = 4
{ n = 4}
ヒープのアルゴリズムによって生成され、各順列は色分けされています（1 =青、2 =緑、3 =黄色、4 =赤）。
Heapのアルゴリズムによって生成されたn個のオブジェクトの順列のシーケンスは、 n +1個のオブジェクトの順列のシーケンスの始まりです。したがって、Heapのアルゴリズムによって生成される順列の無限のシーケンスが1つあります（OEISのシーケンスA280318）。

コンテンツ
1 アルゴリズムの詳細
2 証拠
3 頻繁な誤実装
4 も参照してください
5 参考文献

アルゴリズムの詳細
コレクションの場合 C { C}
$C""$
n個の異なる要素を含むヒープは、各ステップで切り替える要素のペアを選択して、これらの要素のすべての可能な順列を1回だけ生成する体系的な方法を見つけました。
減少と征服の方法として再帰的に説明されるHeapのアルゴリズムは、 k { k}

コレクションの最初の要素。最初はk = n
{ k = n}

その後k < n
{ k
。各ステップで生成されますk ！
{ k！}

同じで終わる順列n − k
{ nk}

最後の要素。これは、自分自身を1回呼び出すことによって行われます。k th
{ k { text {th}}}

要素は変更されず、その後k − 1
{ k-1}

（ k th { k { text {th}}}

）イニシャルごとに交換される要素k − 1
{ k-1}

要素。再帰呼び出しはイニシャルを変更しますk − 1
{ k-1}

要素とルールは、最後と交換されるものを選択するために各反復で必要です。ヒープの方法によると、この選択は、このステップで操作される要素の数のパリティによって行うことができます。もしも k { k}

が偶数の場合、最後の要素は各要素インデックスと繰り返し交換されます。もしも k { k}

奇数の場合、最後の要素は常に最初の要素と交換されます。
procedure generate （k ： integer 、 A ： array of any ）： if k = 1 then
output （A ） else
//k番目を変更せずに順列を生成します//最初に
k =length（A）
generate （k –1 、A ）
// iの各k-1イニシャルでスワップされたk番目の順列を生成します：= 0 ; i < k - 1 ; i + = 1 do // kが偶数の場合はkのパリティ（偶数または奇数）に依存するスワップ選択次にスワップ（A 、A ）//ゼロインデックス、k番目はk- 1 else swap （A 、A ）end if generate （k --1 、A ）end for end if
非再帰的な形式でアルゴリズムを書くこともできます。
プロシージャ生成（n ：整数、 A ：任意の配列）：//cはスタック状態のエンコーディングです。c は、generate（k-1、A）が呼び出されたときのforループカウンターをエンコードします。c ：intの配列
for i ：= 0 ; i < n ; i + = 1 do
c ：= 0 end for 出力（A ）
// iはスタックポインタと同様に動作します i ：= 0 ; while i < n do
if c < i then
if i iseven then swap （A 、 A ）else swap （A [ c ] 、A ）end if output （A ）//スワップが発生し、forループが終了しました。forループカウンターの増分をシミュレートしますc + = 1 //配列内のベースケースアナログへのポインターを持ってくることにより、ベースケースに到達する再帰呼び出しをシミュレートしますi ：= 0 else // generate（i + 1 、A）forループが終了したため終了しました。状態をリセットし、ポインターをインクリメントしてスタックのポップをシミュレートします。c ：= 0 i + = 1 end if end while end

証拠
この証明では、以下の実装をヒープのアルゴリズムとして使用します。最適ではありませんが（以下のセクションを参照）、それでも実装は正しく、すべての順列が生成されます。以下の実装を使用する理由は、分析がより簡単であり、特定のパターンを簡単に示すことができるためです。
プロシージャ生成（k ：整数、 A ：任意の配列）：k = 1の場合、出力（A ）else for i ：= 0 ; i < k ; i + = 1は、 kが偶数の場合は（k --1 、A ）を生成し、スワップ（A 、A ）、それ以外の場合はスワップ（A 、A ）を生成します。
終わりの場合_
主張：配列Aの長さがnの場合、Heapのアルゴリズムを実行すると、Aが1だけ右に「回転」する（つまり、各要素が右にシフトされ、最後の要素が最初の位置を占める）か、Aがnがそれぞれ偶数か奇数かに応じて、変更されません。
根拠：上記の主張は自明に当てはまりますn = 1
{ n = 1}

ヒープのアルゴリズムは、変更されていないAを順番に返すだけです。
誘導：主張が一部に当てはまると仮定するI ≥ 1
{ i geq 1}

。次に、次の2つのケースを処理する必要がI + 1
{ i + 1}

：I + 1
{ i + 1}

偶数または奇数です。
Aの場合、n = I + 1
{ n = i + 1}

が偶数の場合、帰納法の仮説で想定されているように、サブアレイでヒープのアルゴリズムを実行した後、最初のi要素のサブセットは変更されません。サブアレイでHeap’sAlgorithmを実行してから、forループのk番目の反復でスワッピング操作を実行します。k ≤ I + 1
{ k leq i + 1}

、Aのk番目の要素は、一種の「バッファ」と見なすことができるAの最後の位置にスワップされます。最初と最後の要素を交換し、次に2番目と最後の要素を交換することにより、 n番目と最後の要素が交換されるまで、配列は最終的に回転を経験します。上記を説明するために、以下のケースを見てくださいn = 4
{ n = 4}

1，2，3，4…元の配列1，2，3，4 … 1回目の反復（置換サブセット）4，2，3，1 …最初の反復（最初の要素を「バッファ」にスワップします）4，2，3，1 … 2回目の反復（順列サブセット）4，1，3，2 … 2回目の反復（2番目の要素を「バッファ」にスワップ）4，1，3，2 … 3回目の反復（置換サブセット）4，1，2，3 … 3回目の反復（3番目の要素を「バッファ」にスワップ）4，1，2，3 … 4回目の反復（置換サブセット）4，1，2，3 … 4回目の反復（4番目の要素を「バッファ」にスワップ）…変更された配列は元の配列の回転バージョンです
Aの場合、n = I + 1
{ n = i + 1}

が奇数の場合、最初のi要素に対してヒープのアルゴリズムを実行した後、最初のi要素のサブセットが回転します。forループを1回繰り返した後、 AでHeapのアルゴリズムを実行すると、Aが1だけ右に回転することに注意して帰納法の仮説により、最初のi要素が回転すると想定されます。このローテーションの後、Aの最初の要素がバッファーにスワップされ、前のローテーション操作と組み合わせると、本質的に配列でローテーションが実行されます。この回転操作をn回実行すると、アレイは元の状態に戻ります。これは、ケースについて以下に示されていますn = 5
{ n = 5}

。
1，2，3，4，5…元の配列4，1，2，3，5 … 1回目の反復（サブセットの順列/サブセットの回転）5，1，2，3，4 …最初の反復（スワップ）3，5，1，2，4 … 2回目の反復（サブセットの順列/サブセットの回転）4，5，1，2，3 … 2回目の反復（スワップ）2，4，5，1，3 … 3回目の反復（サブセットの順列/サブセットの回転）3，4，5，1，2 … 3回目の反復（スワップ）1，3，4，5，2 … 4回目の反復（サブセットの順列/サブセットの回転）2，3，4，5，1 … 4回目の反復（スワップ）5，2，3，4，1 … 5回目の反復（サブセットの順列/サブセットの回転）1，2，3，4，5 … 5回目の反復（スワップ）…配列の最終状態は元の状態と同じ順序です
これで、クレームの帰納法の証明が完了しました。これにより、Heapのアルゴリズムが配列Aのすべての順列を作成する理由がわかります。もう一度、誘導によってヒープのアルゴリズムの正しさを証明します。
基礎：出力AはAの唯一の順列であるため、ヒープのアルゴリズムはサイズ1の配列Aを自明に順列化します。
誘導：ヒープのアルゴリズムがサイズiの配列を並べ替えると仮定します。前の証明の結果を使用すると、最初のi要素が並べ替えられると、 Aのすべての要素が「バッファー」に1回入れられます。配列の順列は、要素xをAから削除して配列Aを変更し、変更された配列の各順列にxを追加することで作成できるため、Heapのアルゴリズムはサイズの配列を順列化します。I + 1
{ i + 1}

、本質的に「バッファ」は削除された要素を保持し、サイズiのサブアレイの順列に追加されます。ヒープのアルゴリズムの各反復には、サブ配列が並べ替えられるときにバッファーを占めるAの異なる要素があるため、 Aの各要素がバッファー要素なしで配列Aの順列にタックされる可能性があるため、すべての並べ替えが生成されます。

頻繁な誤実装
再帰呼び出しのインスタンスを減らすことによって、上記の再帰バージョンを単純化することは魅力的です。たとえば、次のようになります。
プロシージャ生成（k ：整数、 A ：任意の配列）：k = 1の場合、出力（A ）else
// iのkごとに1回再帰的に呼び出す： = 0 ; i < k ; i + = 1 do generate （k --1 、A ）// kが偶数の場合はk （偶数または奇数）のパリティに応じてスワップの選択// i ==k-1の場合はno- op （A 、A ）else // i == k-1スワップ（A 、A ）の場合のXXXの誤った追加スワップend if
終わりの場合_
この実装は、すべての順列の生成に成功しますが、動きを最小限に抑えることはできません。再帰的なコールスタックがほどけると、各レベルで追加のスワップが発生します。これらの半分は、 A [ I ] { A }

と A [ k− 1 ]
{ A }

どこ I ==k − 1
{ i == k-1}

でもいつ k { k}

奇妙なことに、それは追加のスワップをもたらしますk t h
{ kth}

とともに0 t h {0th}
エレメント。 n { n}
n ！ − 1
{ n！-1}

スワップ
追加=スワップ − （（ n！ − 1 ）。 {-（n！-1）}
1 0 0 0 2 1 1 0 3 10 11 12 13
2327 4 5 119 140 21 6 719 845 270 271 272 273883 8 40319 47383 7064 9 362879 426456 63577
これらの追加のスワップは、k − 1
{ k-1}

プレフィックス要素。
追加のスワップは、ループの前に追加の再帰呼び出しを追加してループすることで回避できます。k − 1
{ k-1}

時間（上記のように）またはループ k { k}

時間とそれをチェックする I { i}

よりも少ないk − 1
{ k-1}

のように：
プロシージャ生成（k ：整数、 A ：任意の配列）：k = 1の場合、出力（A ）else
// iのkごとに1回再帰的に呼び出す： = 0 ; i < k ; i + = 1 do generate （k --1 、A ）// i == k- 1の場合はスワップを回避if （i < k --1 ） // kが偶数の場合はkのパリティに依存するスワップ選択（A 、A ）else swap （A 、A ）end if end if end for end if
選択は主に美的ですが、後者はの値をチェックすることになります I { i}

2倍の頻度で。

も参照してください
Steinhaus–Johnson–Trotterアルゴリズム

参考文献
^ ヒープ、BR（1963）。「インターチェンジによる順列」。コンピュータジャーナル。6（3）：293–4。土井：10.1093 / comjnl/6.3.293。
^ Sedgewick、R.（1977）。「順列生成方法」。ACMコンピューティング調査。9（2）：137–164。土井：10.1145/356689.356692。S2CID12139332。_ ^ セッジウィック、ロバート。「順列生成アルゴリズムに関する講演」（PDF）。”