1. 序章

このチュートリアルでは、配列の順列を生成するための定義、複雑さ、およびアルゴリズムを調べます。

2. 順列

ここで説明する順列は、オブジェクトを位置に配置する方法です。

たとえば、A、B、Cの3文字から単語を検索する必要があるゲームをプレイしているとします。 したがって、単語を作成するためにすべての順列を試します。

これらの6つの順列から、確かに1つの単語があることがわかります。

ただし、この文章題にはわずかな意味上の問題があります。 口語的には、「3文字の組み合わせはいくつ作れるのか」とよく言われます。 問題は、組み合わせと順列は互換性があるかどうかです。 数学的な答えはノーです。

簡単に言えば、順列は、単語の設定とまったく同じように、順序付けられた数字のセットと関係があります。 組み合わせは順序付けられていないセットを扱います。 サイコロのペアを例にとってみましょう。 私たちがそれらを転がすとき、私たちは合計にのみ興味があります。 ラベルは付けていません。 3と4の組み合わせは、4と3の組み合わせと同じです。

2.1. 順列はいくつありますか？

数の順列の数は（階乗）です。  したがって、3つのオブジェクトの場合、順列の数は次のようになります。

 

直感的には、順列を生成するプロセスを再帰的な手順と考えることができます。 最初の位置には、可能性があります（写真の3）。 2番目の位置については、（写真の2）から選択する可能性しかありません。 それぞれのポジションを埋めると、別の可能性が失われます。 したがって、可能性があります。 これは、階乗の定義です。

2.2. 急成長する順列

最後の例で見たように、3つのオブジェクトには6つの可能性があります。 これは管理可能です。b オブジェクトの数が増えると、順列の数が指数関数的に増えます：

4、5、または6文字のセットがある場合、24、120、または720の順列をふるいにかける必要があることがわかります。 順列の数は急速に増加します。

これらの数字がどれほど大きいかを説明するために、トランプのデッキから始めたとしましょう。 組み合わせの数は68桁の数字です（これは自分で計算しませんでした。他の誰かが計算しました）：

80658175170943878571660636856403766975289505440883277824000000000000.

宇宙の年齢はおよそ1013.813歳です。 これは、2.05160945×10 21秒または2.05160945×1030ナノ秒に相当します。 ラスベガスでナノ秒ごとに1回カードをシャッフルできるディーラーを見つけたとしても、宇宙が終わる前に、考えられるすべての組み合わせに近づくことすらできませんでした。

さらに、すべての順列を生成するのにかかる時間は、私たちの唯一の制限ではありません。 たとえば、これらの順列を再帰的に生成するプログラムを作成する場合（以下を参照）、メモリスペースがすぐに不足します。

これは、考えられるすべての順列を生成したい私たちにとっては悪いニュースですが、暗号化にとっては良いニュースです。 たとえば、標準の256暗号化キーには、0と1の1.1 x 10 77の組み合わせがあります。 鍵を見つけようとするのに、私たちには宇宙のいくつかの生涯が必要です。 飼い主の犬の名前や「qwerty」を推測するなど、パスワードを見つける他の方法に頼る必要があります。

2.3. 数学表記

単一の順列の一般的な数学表記は、2行表記です。 ここでは、最初の行に元の配列を表し、2番目の行に要素がどのように変換されるかを示します。

これは順列を表します。

ただし、要素を正規の順序で並べ替えると、順列を1行で記述できます。 この例では、要素の正規の順序は自然数です。

したがって、順列を。として書くことができます。

私たちがよく使用するもう1つの表記法は、順列の構造に光を当てます。 この表記は、循環表記と呼ばれます。 この表記法を使用すると、順列が「サイクル」のセットで表されていることがわかります。 サイクルは、それ自体に戻るサイクルの順列のセットです。 私たちの順列では、2つのサイクルがあることがわかります。 最初のサイクルは次のとおりです。

1が2に並べ替えられ、2が5に並べ替えられますが、5が再び1に並べ替えられることに注意してください。 サイクルがあります：

残りの順列もサイクルであり、3つが4つに順列し、次に4つが3つに戻ります。

これらのサイクルをまとめると、同等の1行の循環表記が得られます。

この表記法にすべての順列を入れることができます。 ただし、1つの問題は、この表記が一意ではないことです。

最大の要素を最初に置くことで、この状況を改善できます。

これは、正規の循環表記と呼ばれます。

3. 単純な再帰的アルゴリズム

前のセクションの図と説明でわかるように、生成順列は、単純な再帰アルゴリズムで定式化できます。 各再帰ステップで、これまでに生成した順列と、順列する残りのオブジェクトのセットがあります。

順列するオブジェクトがなくなったら完了です（残りのオブジェクトリストは空です）。 答えは、これまでに生成された順列です。 この順列を生成された順列の累積リストに追加し、再帰に戻ります。

順列するオブジェクトが残っている場合は、残りのすべてのオブジェクトをループします。 ループ内で、選択したオブジェクトを指定された順列の最後に追加します。 選択したオブジェクトを残りのリストから削除し、新しい順列と新しい残りのリストを再帰的に呼び出します。

このルーチンへの最初の呼び出しは、生成された順列の空のリスト（）、空の順列（）、およびオブジェクトのリスト（）を使用して行われます。 チェックとして、再帰呼び出しごとに残りのリストが小さくなるため、再帰が終了することがわかります。

生成された順列（）および残りのオブジェクト（）構造は、リスト、セット、または配列にすることができます。 これらのオブジェクトは注文する必要はありません。 一方、順列（）では順序が重要であるため、配列である必要があります。

4. ヒープのアルゴリズム

順列を生成するために使用されるより伝統的で効果的なアルゴリズムの1つは、 B。 R。 ヒープ。 このアルゴリズムは、順列を生成するための要素の交換に基づいています 。 これらの要素のすべての可能な順列を1回だけ生成します。

この方法は体系的なアルゴリズムであり、各ステップで、新しい順列を生成するために切り替える要素のペアを選択します。 以前のアルゴリズムとは対照的に、このアルゴリズムの利点は、使用するメモリが少ないことです。

ヒープのアルゴリズムの原理は減少して征服することです。アルゴリズムは基本的に最後の要素で終わるすべての順列を生成します。 次に（n-1）！ 最初のn-1要素の順列は、この最後の要素に隣接しています。 n-1個の要素をループしている間、アルゴリズムには奇数か偶数かに依存する（神秘的な）ステップがあります。

  1. 奇数の場合は、最初と最後の要素を交換します。
  2. 偶数の場合は、（ループ内の）th要素を交換します。

各反復で、アルゴリズムは現在の最後の要素で終わるすべての順列を生成します。

たとえば、4つの要素の場合、シーケンスは次のようになります（左から右への列）。

行Aには、「最後の要素」が表示されます。  行B、C、およびDには、残りの3つの要素の順列があります。 行Bを見ると、最後の2つの要素が並べ替えられていることがわかります。

例を含むより完全な説明は、RuslanまたはJohnsonで見つけることができます。 より数学的な傾向がある場合は、Heapのアルゴリズムが機能する理由についての証拠もあります。 RobertのSedgewickの1977年の順列アルゴリズムのレビューでは、Heapのアルゴリズムが最も単純で最も効率的なものの1つであることがわかりました。

ヒープの元の定式化は非再帰的でしたが、ヒープのアルゴリズムは再帰的または非再帰的な方法で定式化できます。

4.1. 再帰的ヒープのアルゴリズム

再帰バージョンのHeap’sAlgorithmを作成できます。

の値をの値と交換することに注意してください。

重要な実装上の注意は、アレイに関するものです。 ある意味では、は静的配列です。 これは、再帰呼び出しでは、呼び出し元の関数から戻ったときに、サブ呼び出しで発生した配列への変更が残ることを意味します。

4.2. 非再帰的ヒープのアルゴリズム

再帰から派生した非再帰ヒープのアルゴリズムを定義することもできます。 コード内のコメントは、対応を示唆しています。

5. QuickPermアルゴリズム

ヒープのアルゴリズムは伝統的に選択された順列アルゴリズムですが、他のより最近のアルゴリズムがあります。 QuickPermもスワッピングに基づいており、ヒープソートに触発されており、最も効率的なの1つです。 バリエーションと実装については、 QuickPermサイトを参照できますが、ここでは、バージョンの1つ（カウントダウンQuickPerm）の擬似コードを示します。

上記のQuickPermアルゴリズムのプライマリインデックスコントローラー配列はp[N]であり、変数の反復とインデックスの上限を制御します。 それぞれがカウントベースを表します。これもゼロ、ベース2、ベース3などです。 この配列を使用して、生成プロセスを追跡します。 次の要素が考慮されるまで、すべての順列は「下位」要素で形成されます。

順列を使用したp行列の開発例を次に示します。

ここでは、下（左）の順列が最初にどのように発達するかを見ることができます。 の場合、最初の3つのp要素がゼロのとき、すべての順列を作成しました。

完全なアルゴリズムは次のとおりです。

たとえば、 JAVA 、 python 、 C ++ 、およびGoにQuickPermアルゴリズムの実装があります。

6. 辞書式順序の順列

辞書式順序は、たとえばアルファベット順を一般化したものです。 辞書式順序を確立するための鍵は、一連の順序付け関数（、、、など）の定義です。 これらの関数は、データ型に適した方法で定義できます。

通常の>、<、および==演算子の代わりに関数のセットが指定されている場合（またはオブジェクト指向言語ではオーバーライドされている場合）、配列は任意のオブジェクトにすることができます。 たとえば、人々の名前を表す構造の配列があるとします。 名と姓の2つのフィールドがあります。 順序付け関数は、最初に名前を調べます。 2人の名前が同じである場合、順序付け関数は名を調べます。

Edsger W.Dijkstra in A Discipline of Programming（1976）によって定式化された辞書式順序アルゴリズムは、次のように定式化できます。

  • <のような最大のインデックスを見つけます（そのようなものが存在しない場合、これはすでに最後の順列です）
  • 次のような最大のインデックスを見つける
  • 交換して
  • で始まる接尾辞を逆にします

このアルゴリズムは、次の辞書式順列を返します。 入力が最大の場合、配列は変更されずに返されます。 興味深いことに、要素を繰り返した場合、アルゴリズムはそれらをスキップしてシリーズの次の要素を見つけます。

7. 結論

この記事では、順列とそれらを計算するために使用できるアルゴリズムを確認しました。 順列の数は要素の数とともに急速に増加するため、効率的な実装が重要であることがわかりました。 結果として、再帰は本質的に多くのメモリスペースを使用するため、非再帰的な方法をお勧めします。

ヒープの並べ替えアルゴリズムとQuickPermアルゴリズムの2つの方法を紹介しました。 これらのアルゴリズムは特定の順序で順列を生成しませんが、辞書式順序で順列を与える別のクラスの順列アルゴリズムを提示しました。