順列

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
6つの行のそれぞれは、3つの異なるボールの異なる順列です。

数学は、セット順列は、大まかに言えば、そのメンバーをシーケンスまたは線形順序に配置すること、またはセットがすでに順序付けられている場合は、その要素を再配置することです。「順列」という言葉は、順序集合の線形順序を変更する行為またはプロセスも指します。[1]

順列は、順序に関係なくセットの一部のメンバーの選択である組み合わせとは異なります。たとえば、タプルとして記述された場合、集合{1、2、3}には6つの順列があります。つまり、(1、2、3)、(1、3、2)、(2、1、3)、(2、 3、1)、(3、1、2)、および(3、2、1)。これらはすべて、この3要素セットの可能な順序です。文字が異なる単語のアナグラムも順列です。文字は元の単語ですでに順序付けられており、アナグラムは文字の並べ替えです有限集合の順列の研究は、組み合わせ論と群論の分野で重要なトピックです。

順列は、数学のほぼすべての分野、および他の多くの科学分野で使用されています。コンピュータサイエンスでは、並べ替えアルゴリズムの分析に使用されます量子物理学は、粒子の状態を記述するため。生物学では、 RNA配列 を記述するために。

n個の異なるオブジェクトの順列の数はn 階乗であり、通常はn!と記述されます。、これは、 n以下のすべての正の整数の積を意味します

技術的には、集合 Sの順列は、Sからそれ自体への全単射として定義されます。[2] [3] つまり、すべての要素が画像として1回だけ出現するSからSまでの関数です。これは、各要素sが対応するfsに置き換えられたSの要素の再配置に関連しています。たとえば、上記の順列(3、1、2)は、関数によって記述されます。として定義

セットのすべての順列のコレクションは、セットの対称群と呼ばれるグループを形成します。グループ操作は構成(2つの指定された再配置を連続して実行する)であり、その結果、別の再配置が行われます。順列のプロパティはセット要素の性質に依存しないため、多くの場合、セットの順列です。順列を研究するために考慮されます。

基本的な組み合わせ論では、k順列、または部分順列は、セットから選択されたk個の異なる要素の順序付けられた配置です。kがセットのサイズと等しい場合、これらはセットの順列です。

1974年にErnőRubikによって発明された人気のパズルRubikの立方体では、パズルの面が回転するたびに、表面の色が変化します。

歴史

六十四卦と呼ばれる順列は、紀元前1000年 に易経拼音:李京)で中国で使用されました。

アラブの数学者暗号学者のAl-Khalil(717–786)は、暗号メッセージの本を書きましたこれには、母音がある場合とない場合のすべての可能なアラビア語をリストするための、順列と組み合わせの最初の使用が含まれています。[4]

n個のオブジェクトの順列の数を決定する規則は、1150年頃のインドの文化で知られていました。インドの数学者バースカラ2世によるリラヴァティには、次のような一節が含まれています。

算術級数の乗算の積は、1で始まり、1ずつ増加し、場所の数まで続き、特定の数値による数の変化になります。[5]

1677年、ファビアンステッドマンは、チェンジリンギングにおけるベルの順列の数を説明するときに階乗について説明しました2つの鐘から始めて:「最初に、2つは2つの方法で変化することを認めなければならない」、それは彼が12と21を示すことによって説明 します。再び示されている3 "から生成されます。彼の説明には、「キャストアウェイ3、1.2が残る、キャストアウェイ2、1.3が残る、キャストアウェイ1、2.3が残る」が含まれます。[7] 次に、彼は4つのベルに移動し、キャストアウェイの議論を繰り返して、3つの異なるセットが4つあることを示します。事実上、これは再帰的なプロセスです。彼は「キャストアウェイ」方式を使用して5つのベルを続け、結果の120の組み合わせを表にまとめます。[8] この時点で、彼はあきらめて次のように述べています。

現在、これらのメソッドの性質は、1つの数値の変更が、すべての小さい数値の変更を理解するというものです。1つの数値の変更の完全なピールは、すべての小さい数値の完全なピールを結合することによって形成されるように見えます。 1つの全身に; [9]

Stedmanは順列の考慮を広げます。彼はさらに、20の厩舎からのアルファベットの文字と馬の順列の数を検討します。[10]

一見無関係な数学的質問が順列の助けを借りて研究された最初のケ​​ースは、ジョセフ・ルイ・ラグランジュが多項式の研究で、方程式のの順列の特性が可能性に関連していることを観察した1770年頃に発生しましたそれを解決します。この一連の作業は、最終的には、ガロア理論におけるエヴァリストガロアの作業を通じてもたらされました。これは、ラジカルによる多項式(1つの未知数)の解法に関して可能なことと不可能なことの完全な説明を提供します。現代の数学では、問題を理解するためにそれに関連する特定の順列を研究する必要がある多くの同様の状況があります。

繰り返しのない順列

順列の最も簡単な例は、繰り返しのない順列です。ここでは、 n個のアイテムをnの場所に配置するための可能な方法の数を検討します。階乗は、繰り返しを含まないセット内の順列の数を定義する際に特別な用途があります。「n階乗」と読み替えられる数n!は、正確には、n個の物を新しい順序に並べ替えることができる方法の数です。たとえば、オレンジ、リンゴ、ナシの3つの果物がある場合、上記の順序で食べることも、変更することもできます(たとえば、リンゴ、ナシ、オレンジ)。順列の正確な数は次のようになりますアイテム数(n)が増えると、その数は非常に大きくなります。

同様に、n個のオブジェクトからのk個のアイテムの配置の数は、部分順列またはk順列と呼ばれることもありますそれは次のように書くことができます(これは「npermute k」と読みます)、そして数に等しい(また、)。[11] [12]

定義

数学のテキストでは、小文字のギリシャ文字を使用して順列を示すのが通例です。一般的に、どちらか、 また使用されています。[13]

順列は、集合Sからそれ自体への全単射として定義できます。n個の要素を持つセットのすべての順列は、対称群を形成します。、ここで、グループ操作関数合成です。したがって、2つの順列の場合、グループで、4つのグループ公理が成り立ちます:

  1. 閉鎖:もしにありますそれならそうです
  2. 結合性:任意の3つの順列に対して
  3. アイデンティティ:アイデンティティの順列があり、によって定義されますすべてのために任意の
  4. 可逆性:すべての順列に対して、 が存在しますとなることによって

一般に、2つの順列の合成は可換ではありません。つまり、

セットからそれ自体への全単射として、順列はセットの再配置を実行する関数であり、再配置自体ではありません。より古く、より基本的な視点は、順列は再配置そのものであるということです。これら2つを区別するために、アクティブパッシブの識別子が順列という用語の前に付けられることがありますが、古い用語では置換順列が使用されます。[14]

順列は、1つまたは複数の互いに素なサイクル、つまり、いくつかの要素への順列の適用を繰り返しトレースすることによって検出される軌道に分解できます。たとえば、順列によって定義されます1サイクルあり、順列がによって定義されます2サイクルあり(構文の詳細については、以下の§サイクル表記を参照してください)。一般に、長さkのサイクル、つまりk個の要素で構成されるサイクルはkサイクルと呼ばれます

1サイクルの要素順列の不動点と呼ばれます。不動点のない順列は、完全順列と呼ばれます。2サイクルは転置と呼ばれます; このような順列は、2つの要素を交換するだけで、他の要素は固定されたままになります。

表記

順列を要素ごとに、つまり区分的関数として書くのは面倒なので、それらをよりコンパクトに表すためにいくつかの表記法が発明されました。サイクル表記は、そのコンパクトさと順列の構造を透過的にするという事実のために、多くの数学者に人気のある選択肢です。特に指定がない限り、この記事で使用されている表記法ですが、特にアプリケーション分野では、他の表記法も広く使用されています。

2行表記

コーシー2行表記では、[15] 1つは最初の行にSの要素をリストし、それぞれについて2番目の行にその下の画像をリストします。たとえば、集合S = {1、2、3、4、5}の特定の順列は次のように書くことができます。

これは、σがσ(1)= 2σ(2)= 5σ(3)= 4σ(4)= 3、およびσ(5)= 1を満たすことを意味します。Sの要素は、最初の行に任意の順序で表示できます。この順列は、次のように書くこともできます。

また

1行表記

Sの要素に「自然な」順序がある場合[a]は言います、次に、これを2行表記の最初の行に使用します。

この仮定の下では、最初の行を省略して、順列を1行表記で 次のように書くことができます。

つまり、Sの要素の順序付けられた配置として。[16] [17] 1行表記と以下に説明するサイクル表記を区別するように注意する必要があります。数学の文献では、一般的な使用法は、1行表記の括弧を省略し、サイクル表記には括弧を使用することです。1行表記は、順列の単語表現とも呼ばれます。[18]最初の行には自然次数12 3 4 5が想定されるため、上記の例は2 5 4 31になります。(2桁以上のエントリがある場合にのみ、これらのエントリをコンマで区切るのが一般的です。)この形式はよりコンパクトで、基本的な組み合わせ論で一般的です。コンピュータサイエンスこれは、 Sの要素または順列をより大きくまたはより小さく比較する アプリケーションで特に役立ちます。

サイクル表記

サイクル表記は、セットの要素に順列を繰り返し適用する効果を表します。これは、順列をサイクルの積として表現します。別個のサイクルは互いに素であるため、これは「互いに素なサイクルへの分解」と呼ばれます。

順列を書き留めるにはサイクル表記では、次のように進みます。

  1. 開き角かっこを書き、任意の要素xを選択します。そしてそれを書き留めます:
  2. 次に、 xの軌道をトレースします。つまり、の連続したアプリケーションの下でその値を書き留めます
  3. 値がxに戻るまで繰り返し、xではなく閉じ括弧を書き留めます。
  4. 次に、まだ書き留められていないSの要素yを続行し、同じ方法で続行します。
  5. Sのすべての要素がサイクルで書き込まれるまで繰り返します。

したがって、順列2 5 4 3 1(1行表記)は、サイクル表記では (125)(34)と書くことができます。

一般に順列は通勤しませんが、互いに素なサイクルは通勤します。例えば、

さらに、各サイクルは、異なる開始点を選択することにより、異なる方法で記述することができます。例えば、
これらの等式を組み合わせて、与えられた順列の互いに素なサイクルを多くの異なる方法で書くことができます。

1サイクルは、コンテキストが明確である場合、サイクル表記から省略されることがよくあります。Sの要素xどのサイクルにも現れない場合、暗黙的に[19] 1サイクルのみで構成される単位順列は、単一の1サイクル(x)、番号1、[b]、またはidで表すことができます。[20] [21]

サイクル表記の便利な機能は、順列の逆のサイクル表記が、順列のサイクル内の要素の順序を逆にすることによって与えられることです。例えば、

標準的なサイクル表記

いくつかの組み合わせの文脈では、サイクル内の要素と(互いに素な)サイクル自体の特定の順序を修正すると便利です。MiklósBónaは、次の順序の選択肢を標準的なサイクル表記と呼んでいます。

  • 各サイクルで、最大の要素が最初にリストされます
  • サイクルは最初の要素の昇順でソートされます

たとえば、(312)(54)(8)(976)は、正規のサイクル表記の順列です。[22]正規のサイクル表記では、1サイクルが省略されていません。

リチャード・P・スタンレーは、同じ表現の選択を順列の「標準表現」と呼んでいます。[23]そしてMartinAignerは、同じ概念に「標準形」という用語を使用しています。[18]セルゲイ・キタエフも「標準形」の用語を使用していますが、両方の選択を逆にしています。つまり、各サイクルは最小の要素を最初にリストし、サイクルは最小の要素、つまり最初の要素の降順でソートされます。[24]

順列の構成

2つの順列の構成を示すには2つの方法があります。セットの任意の要素xをにマップする関数です 関数適用の記述方法のため、 右端の順列が最初に引数に適用されます[25] 。

関数の合成結合法則であるため、順列の合成演算も結合法則です。したがって、3つ以上の順列の積は、通常、グループ化を表すために括弧を追加せずに記述されます。また、通常、構成を示すためにドットやその他の記号なしで書かれています。

一部の著者は、最初に作用する左端の因子を好む[26] [27] [28]が、そのためには、 xに作用するσがと書かれる指数として、 順列を引数の右側に記述する必要がありますその場合、積は・π =(π定義されます。ただし、これにより、順列を乗算するための別のルールが提供されます。この記事では、右端の順列が最初に適用される定義を使用します。

順列という用語の他の使用法

順序付けられた配置としての順列の概念は、順列ではないが、文献では順列と呼ばれているいくつかの一般化を認めています。

k - nの順列

順列という用語のより弱い意味は、基本的な組み合わせ論のテキストで使用されることがあり、要素が2回以上出現しないが、特定のセットのすべての要素を使用する必要がない順序付けられた配置を示します。これらは、特別な場合を除いて順列ではありませんが、順序付けられた配置の概念の自然な一般化です。実際、この使用には、サイズnの特定のセットから取得された要素の固定長 kの配置を考慮することが含まれることがよくあります。つまり、 nのこれらのk順列は、 nセットのk要素サブセットの異なる順序の配置です。 バリエーション または古い文献の取り決め[c])。これらのオブジェクトは、部分順列または繰り返しのないシーケンスとしても知られています。これは、他のより一般的な「順列」の意味との混同を避ける用語です。そのような数-の順列次のような記号でさまざまに示されます、 また、およびその値は、製品[29]によって与えられます。

これは、 k > nの場合は0であり、それ以外の場合は 次のようになります。

製品は、次のことを前提とせずに明確に定義されていますは非負の整数であり、組み合わせ論以外でも重要です。それはポッホハンマーのシンボルとして知られています またはとして-階乗冪力

順列という用語のこの使用法は、組み合わせという用語と密接に関連しています。nセットSk要素の組み合わせは、Sk要素サブセットであり、その要素は順序付けられていません。Sのすべてのk要素サブセットを取得し、それらのそれぞれをすべての可能な方法で順序付けることにより、 Sのすべてのk順列を取得します。したがって、 nセットCnk )のkの組み合わせの数は、kの数に関連しています。-nの順列

これらの数値は二項係数とも呼ばれ、次のように表されます。

繰り返しのある順列

繰り返しが許可されている集合Sのn個の要素の順序付けられた配置は、 nタプルと呼ばれます。それらは一般に順列ではありませんが、繰り返しを伴う順列と呼ばれることもあります。文脈によっては、アルファベットSの上の単語とも呼ばれます。セットSk個の要素がある場合、S上のnタプルの数はようになります。要素がnタプルに 表示される頻度に制限はありませんが、要素が表示される頻度に制限がある場合、この式は無効になります。

マルチセットの順列

マルチセットの順列

Mが有限多重集合である場合多重集合順列はMの要素の順序付けられた配置であり、各要素はMの多重度に正確に等しい回数出現します。いくつかの繰り返される文字を含む単語のアナグラムは、マルチセット順列の例です。[d] Mの要素の多重度(ある順序で取得)が、...、そして、それらの合計(つまり、Mのサイズ)がnである場合、 Mの多重集合順列の数は多項係数[30]によって与えられます。

たとえば、MISSISSIPPIという単語の個別のアナグラムの数は次のとおりです。[31]

マルチセットMのk順列は、Mの要素の長さkのシーケンスであり、各要素はMの多重要素繰り返し以下回数表示れます。

巡回置換

順列は、配置と見なされる場合、線形順序配置と呼ばれることもあります。これらの配置には、第1の要素、第2の要素などがあります。ただし、オブジェクトが円形に配置されている場合、この区別された順序はもはや存在しません。つまり、配置に「最初の要素」がない場合、任意の要素を配置の開始と見なすことができます。循環的なオブジェクトの配置は、循環順列と呼ばれます。[32] [e]これらは、線形配置の最後の要素をその前に移動することによって生成される 同値関係について、オブジェクトの通常の順列の同値類として正式に定義できます。

一方を他方に回転させることができる場合(つまり、要素の相対位置を変更せずに循環させることができる場合)、2つの循環順列は同等です。次の4文字の4つの循環順列は、同じであると見なされます。

     1 4 2 3
   4 3 2 1 3 4 1 2
     2 3 1 4

円形の配置は反時計回りに読み取られるため、回転によって一方が他方に移動することはできないため、次の2つは同等ではありません。

     1 1
   4 3 3 4
     2 2

n個の要素を持つ集合Sの巡回置換の数は(n  – 1)! です。

プロパティ

n個の異なるオブジェクトの順列の数はn!です。

k個の互いに素なサイクルを持つn個の順列の数は、 cnkで表される第1種の符号なしスターリング数です[33]

順列タイプ

順列のサイクル(固定小数点を含む)n個の要素を持つセットのそのセットを分割します。したがって、これらのサイクルの長さはnのパーティションを形成します。これは、のサイクルタイプ呼ばれます。のすべての不動点のサイクルタイプには「1」があります、すべての転置に対して「2」など。のサイクルタイプ

これは、よりコンパクトな形式で[1 1 2 2 31 ]書くこともできます。より正確には、一般的な形式は、 どこそれぞれの長さのサイクル数です。特定のタイプの順列の数は[34]です。

活用順列

一般に、サイクル表記で書かれた作曲順列は、簡単に説明できるパターンには従いません。作曲のサイクルは、作曲されているものとは異なる場合があります。ただし、順列を活用する特殊なケースでは、サイクル構造は保持されます。別の順列によって、これは製品を形成することを意味しますここ、共役ですそして、そのサイクル表記は、次のサイクル表記を取ることによって取得できます。と適用その中のすべてのエントリに。[35]したがって、2つの順列は、同じタイプの場合に正確に共役になります。

順列順

順列の順序は最小の正の整数mであるため、これは、サイクル長の最小公倍数です。たとえば、

順列のパリティ

有限集合のすべての順列は、転置の積として表すことができます。[36] 与えられた順列に対するそのような表現はたくさん存在するかもしれませんが、それらはすべて偶数または奇数の転置を含んでいます。したがって、すべての順列は、この数に応じて 偶数または奇数に分類できます。

この結果は、書かれた記号を割り当てるように拡張することができます、各順列に。もしも偶数でありもしも奇妙です。次に、2つの順列について

その結果

行列表現

順列行列は、各列と各行に1つのエントリ1があり、他のすべてのエントリは0であるn × n 行列です。置換行列を{1の順列に割り当てるために使用できるいくつかの異なる規則があります。 、2、...、n }。自然なアプローチの1つは、順列σに行列を関連付けることです。その(ij)エントリは、i = σj)の場合は1であり、それ以外の場合は0です。この規則には2つの魅力的な特性があります。1つは、行列と順列の積が同じ順序である、つまり、すべての順列σおよびπに対して。第二に、標準を表します 列ベクトルi番目のエントリが1に等しく、他のすべてのエントリが0に等しいベクトル)、次に

たとえば、この規則では、順列に関連付けられた行列および順列に関連付けられた行列次に、順列の構成は次のとおりです。、および対応する行列積は

順列行列の乗算に対応する順列の合成。

順列σが行列に関連付けられている逆規則を見つけることも文献で一般的ですその(ij)エントリは、j = σi)の場合は1であり、それ以外の場合は0です。この規則では、順列行列は順列とは逆の順序で乗算されます。すべての順列σおよびπに対して。この対応では、置換行列は標準のインデックスを置換することによって機能します行ベクトル:1つは

右側 Cayley表は、3つの要素の順列に対するこれらの行列を示しています。

Foataの遷移補題

単線表記と標準サイクル表記には関係があります。順列を検討する、標準的なサイクル表記では、そのサイクル括弧を消去すると、順列が得られます1行表記で。Foataの遷移補題は、この対応の性質を、(それ自体への)n順列のセットに対する全単射として確立します。[37] リチャード・P・スタンレーは、この対応を基本的な全単射と呼んでいます。[23]

させてかっこを消す変換になります。の逆少し直感的ではありません。1行表記から始める、正規サイクル表記の最初のサイクルは、で開始する必要があります後続の要素が、私たちは同じサイクルにいます。2番目のサイクルは最小のインデックスから始まりますそのような言い換えると、左にある他のすべてよりも大きいため、左から右への最大値と呼ばれます。正規のサイクル表記のすべてのサイクルは、左から右への最大値から始まります。[37]

たとえば、1行表記で、5は3より大きい最初の要素であるため、最初のサイクルは次に、8は5より大きい次の要素であるため、2番目のサイクルは次のようになります。9は8より大きいのでそれ自体がサイクルです。最後に、9は右側の残りのすべての要素よりも大きいため、最後のサイクルは次のようになります。

の6つの順列正規のサイクルマップは次のとおりです。

最初の結果として、正確にk個の左から右への最大値を持つn順列の数も、第1種の無符号のスターリング数に等しくなります。さらに、Foataのマッピングは、k -1の上昇を伴うn-順列へのk-弱い過剰を伴うn-順列を取ります。[37] たとえば、(2)(31)= 321には2つの弱いエクセダンス(インデックス1と2)がありますが、f(321)= 231には1つの上昇(インデックス1、つまり2から3)があります。

全順序集合の順列

一部のアプリケーションでは、並べ替えられるセットの要素が互いに比較されます。これには、任意の2つの要素を比較できるように、集合S全順序である必要があります。セット{1、2、...、n }は、通常の「≤」関係によって完全に順序付けられているため、これらのアプリケーションで最も頻繁に使用されるセットですが、一般に、完全に順序付けられたセットであればどれでもかまいません。これらのアプリケーションでは、順列内の位置について話すために、順列の順序付けられた配置ビューが必要です

Sの合計順序に直接関連するプロパティがいくつかあります

上昇、下降、走行、および超過

n順列 σ上昇は、次の値が現在の値よりも大きい任意の位置i  <  nです。つまり、 σ  =  σ1σ2 ... σnの場合、 σi  <  σi + 1場合i上昇です

たとえば、順列3452167には、(位置で)1、2、5、および6の上昇があります。

同様に、降下は位置i  <  nであり、σi  >  σi + 1あるため、すべてiσの上昇または下降のいずれかです 

順列の昇順の実行は、どちらの端でも拡張できない順列の空ではない増加する連続したサブシーケンスです。これは、連続する上昇の最大シーケンスに対応します(後者は空の場合があります。2つの連続する下降の間には、長さ1の上昇ランがあります)。対照的に、順列の増加するサブシーケンスは必ずしも連続しているわけではありません。それは、いくつかの位置の値を省略することによって順列から取得される要素の増加するシーケンスです。たとえば、順列2453167には昇順の実行245、3、および167があり、増加するサブシーケンス2367があります。

順列にk−  1の降下がある場合、それはk個の昇順の実行の和集合でなければなりません。[38]

k個の上昇を伴うnの順列の数は、(定義により)オイラー数です。 ; これは、 k個の降下を持つnの順列の数でもあります。ただし、一部の著者はオイラー数を定義していますk − 1の降下に対応する、 kの昇順の実行による順列の数として。[39]

順列σ1σ2...σn超過 σj > jなるようインデックスjです不等式が厳密でない場合(つまり、σj≥j)、j弱い標準偏差呼ばれますk個の過剰を持つn個の順列の数は、 k個の降下を持つn個の順列の数と一致します。[40]

反転

15パズルの目標は、正方形を昇順で取得することです。反転数が奇数の初期位置を解くことは不可能です。[41]

順列 σ反転は、順列のエントリが反対の順序にある​​位置のペアij)です。[42] したがって、降下は2つの隣接する位置での反転にすぎません。たとえば、順列σ = 23154には、エントリ(2、1)、(3、1)、および(のペアに対して、(1、3)、(2、3)、および(4、5)の3つの反転があります。 5、4)。

反転は、順序が逆になっているのペア(σi、σjとして定義れる場合があります。これは、反転の数に違いはなく、このペア(反転)は、逆順列σ -1の上記の意味での反転でもあります。転倒の数は、順列のエントリが故障している程度の重要な尺度です。σσ −1についても同じです連続して適用することにより、 k個の転倒を伴う順列を順序付ける(つまり、それを単位元順列に変換する)(右乗算)隣接する転置は常に可能であり、k個のそのような操作のシーケンスを必要とします。さらに、隣接する転置の合理的な選択が機能します。各ステップで、ii + 1の転置を選択するだけで十分です。ここで、iは、これまでに変更された順列の降下です(転置によって、この特定の降下が削除されます。他の降下を作成する可能性がありますが)。これは、このような転置を適用すると、転倒の数が1つ減るためです。この数がゼロでない限り、順列はアイデンティティではないため、少なくとも1つの降下があります。バブルソート挿入ソートシーケンスを整理するためのこの手順の特定のインスタンスとして解釈できます。ちなみに、この手順は、任意の順列σが隣接する転置の積として記述できることを証明しています。これは、 σをアイデンティティに変換するような転置のシーケンスを単純に逆にすることができるためです。実際、 σをアイデンティティに変換する隣接する転置のすべてのシーケンスを列挙することにより、隣接する転置の積として σを書き込む最小長のすべての式の完全なリストを(反転後に)取得します。

k個転倒を伴うnの順列の数は、マホニアン数で表されます[43]。これは、積の展開における Xkの係数です。

これは(Xの代わりにqを使用して)q階乗[ n ] qとしても知られています!製品の拡張はネックレス(組み合わせ論)に表示されます。

させてそのようなこの場合、反転の重みを言います小林(2011)は列挙式を証明した

どこ対称群のブリュア順序を示します。この段階的な半順序は、コクセター群のコンテキストでよく見られます。

コンピューティングにおける順列

順列の番号付け

n個の順列を表す1つの方法は、 0≤N   <  n !の整数Nを使用することです。ただし、順列の数と表現を順序付けられた配置(シーケンス)として変換するための便利な方法が提供されます。これにより、任意の順列を最もコンパクトに表現できます。コンピューティングでは、nがマシンワードで保持できるほど小さい場合に特に魅力的です。32ビットワードの場合、これはn≤12を意味 し、64ビットワードの場合、これはn≤20を意味します変換 は、数列d ndnの中間形式を介して実行できます。−1、...、d 2d 1、ここで、d iはi未満の非負の整数です( d 1は常に0であるため、省略できますが、その存在により、その後の順列への変換が容易になります。説明)。次に、最初のステップは、階乗数システムでNを単純に表現することです。これは、特定の混基数表現です。ここで、 n !未満の数の場合、連続する桁の底(場所の値または乗算係数)はn − 1 )です。 )!n − 2)!、...、2!、1!。2番目のステップでは、このシーケンスをレーマーコードまたは(ほぼ同等に)反転テーブルとして解釈します。

のロス図
σi _
1 2 3 4 5 6 7 8 9 レーマーコード
1 ×× ×× ×× ×× ×× •• d 9 = 5
2 ×× ×× •• d 8 = 2
3 ×× ×× ×× ×× ×× •• d 7 = 5
4 •• d 6 = 0
5 ×× •• d 5 = 1
6 ×× ×× ×× •• d 4 = 3
7 ×× ×× •• d 3 = 2
8 •• d 2 = 0
9 •• d 1 = 0
反転テーブル 3 6 1 2 4 0 2 0 0

順列 σレーマーコードでは、数d nは第1項 σ1に対して行われた選択を表し、数d n -1は、セットの残りのn −1要素の中から第2σ2に対して行われた選択を表します。 、など。より正確には、各d n + 1- iは、残りの要素の数を項σiよりも厳密に少なくします。それらの残りの要素は、後の項σjとして現れるはずなので、数字d n + 1- iは、 iを含む反転ij)を小さいインデックス( i  <  jおよびσi  >  σjであるjの数としてカウントしますσ反転テーブルは 非常に似ていますが、ここでd n + 1- kは、反転(ij)の数をカウントします。ここで、k  =  σjは、反転した順序で表示される2つの値の小さい方として発生します[44]両方 のエンコーディングは、(i  σi ドットが順列 のエントリをマークi σ j)は反転をマークします( i j); 反転の定義により、列のドット( j σj )の前とドット( i σi の両方の前にある正方形に十字が表示されます)その行に。レーマーコードは連続する行のクロスの数をリストし、反転テーブルは連続する列のクロスの数をリストします。これは、逆順列のレーマーコードであり、その逆も同様です。

レーマーコードdn 、d n -1 ... d 2 d 1を順序集合Sの順列に効果的に変換するには、 Sの要素のリストから昇順で開始できます 1からnに増加して、 d n + 1- iの他の要素が前にあるリスト内の要素にσiを設定し、その要素をリストから削除します。反転テーブルを変換するにはdn d n −1 ...d2d 1を対応する順列に入れると、 Sの要素を最初は空のシーケンスに挿入しながら、 d1からdnまでの数値をトラバースできます。反転テーブルの番号dを使用するステップで、 Sの要素が、すでに存在するd個の要素が先行するポイントでシーケンスに挿入されます。あるいは、反転テーブルの数値とSの要素の両方を逆の順序で処理し、 n個の空のスロットの行から始めて、各ステップでSの要素を配置することもできます。d他の空のスロットが先行する空のスロットに。

連続する自然数を階乗数システムに変換すると、それらのシーケンスが辞書式順序で生成され(混合基数システムの場合と同様)、さらにそれらを順列に変換すると、レーマーコード解釈が使用される場合(反転テーブルを使用)、辞書式順序が保持されます。 、別の順序になります。最初のエントリの値ではなく、エントリ1の場所で順列を比較することから始めます)。階乗数法表現の数の合計は順列の反転の数を与え、その合計のパリティは署名を与えます順列の。さらに、反転テーブルのゼロの位置は、順列の左から右への最大値(例6、8、9)を示しますが、レーマーコードのゼロの位置は右の位置です。 -左への最小値(この例では、値1、2、5の4、8、9を配置します)。これにより、すべての順列間でそのような極値の分布を計算できます。レーマーコードdnd n −1、...、d 2d 1の順列は、di≥di + 1場合に限り上昇n −iを持ちます

順列を生成するアルゴリズム

計算では、値の特定のシーケンスの順列を生成する必要がある場合があります。これを行うのに最適な方法は、ランダムに選択された順列が必要か、すべての順列が必要か、後者の場合は特定の順序が必要かどうかによって異なります。もう1つの問題は、特定のシーケンスのエントリ間で可能な同等性を考慮に入れるかどうかです。その場合、シーケンスの個別のマルチセット順列のみを生成する必要があります。

nの順列を生成する明白な方法は、レーマーコードの値を生成し(おそらくnまでの整数の階乗記数法表現を使用して!)、それらを対応する順列に変換することです。ただし、後者のステップは簡単ですが、シーケンスからの選択とシーケンスからの削除のそれぞれを任意の位置でn回実行する必要があるため、効率的に実装するのは困難です。配列またはリンクリストとしてのシーケンスの明白な表現のうち、両方とも(さまざまな理由で)変換を実行するために約n2 / 4の操作を必要とします。nかなり小さい可能性があり(特にすべての順列の生成が必要な場合)、それほど問題にはなりませんが、ランダム生成と体系的生成の両方で、かなり優れた単純な代替手段があることがわかります。このため、確かに可能ではありますが、 On log n時間 でレーマーコードから順列への変換を実行できる特別なデータ構造を採用することは有用ではないようです。

順列のランダム生成

nの特定のシーケンスのランダム順列を生成する場合、ランダムに選択されたnの順列をシーケンスに適用するか、シーケンスの個別の(マルチセット)順列のセットからランダム要素を選択するかは関係ありません。これは、繰り返される値の場合、同じ順列シーケンスをもたらすnの多くの異なる順列が存在する可能性がある場合でも、そのような順列の数は、可能な結果ごとに同じであるためです。数n !の増加により大きなnに対して実行不可能になる体系的な生成とは異なり、ランダム生成に対してnが小さいと 仮定する理由はありません。

ランダム順列を生成する基本的な考え方は、n!の1つをランダムに生成することです。0≤di < iを満たす整数d1d 2、...、d nのシーケンスd 1は常にゼロであるため、省略できます)、全単射対応によって順列変換ます後者の対応では、(逆)シーケンスをレーマーコードとして解釈できます。これにより、1938年にRonaldFisherとFrankYatesによって最初に公開された生成方法がられます[46] 当時、コンピューターの実装は問題ではありませんでしたが、このメソッドは、レーマーコードから順列に効率的に変換するために上記でスケッチした難しさに悩まされています。これは、別の全単射対応を使用することで解決できます。diを使用して、シーケンスの残りのi個の要素から要素を選択した後(i値を減らすため)、要素を削除して、さらに要素を1つ下にシフトしてシーケンスを圧縮するのではなく、 、1つのスワップ最後に残っている要素を持つ要素。したがって、選択のために残っている要素は、元のシーケンスと同じ順序で発生しない場合でも、各時点で連続した範囲を形成します。整数のシーケンスから順列へのマッピングはやや複雑ですが、即時の誘導によって、正確に1つの方法で各順列を生成することがわかります。選択した要素がたまたま最後の残りの要素である場合、スワップ操作は省略できます。これは、条件のテストを保証するほど頻繁には発生しませんが、すべての順列を生成できることを保証するために、最終要素を選択の候補に含める必要があります。

のランダム順列を生成するための結果のアルゴリズムは、擬似コードで次のように記述できますa[0], a[1], ..., a[n − 1]

 nから2までiの場合 dodi ←{0、...、i −1}のランダム要素a
     [ di ]a [ i −1
 ]交換ます  
     

これは、次 のようにアレイの初期化と組み合わせることができますa[i] = i

for  i  from 0 to  n −1 do 
    d i + 1 ←ランダム要素{0、...、i }
     a [ i ]← a [ d i +1 ]
     a [ d i + 1 ]← i

d i +1 = iの場合、最初の割り当ては初期化されていない値をコピーしますが、2番目の割り当ては正しい値iで上書きします。

ただし、Fisher-Yatesは本質的に順次アルゴリズムであり、「分割統治」手順で同じ結果を並行して達成できるため、Fisher-Yatesは順列を生成するための最速のアルゴリズムではありません。[47]

辞書式順序での生成

特定のシーケンスのすべての順列を体系的に生成する方法はたくさんあります。[48] 1つの古典的で単純で柔軟なアルゴリズムは、辞書式順序で次の順列が存在する場合はそれ を見つけることに基づいています。繰り返される値を処理できます。その場合、個別のマルチセット順列を1回ずつ生成します。通常の順列の場合でも、辞書式順序でレーマーコードの値を生成し(おそらく階乗数法を使用して)、それらを順列に変換するよりもはるかに効率的です。シーケンスを(弱く)増加させてソートすることから始まります順序(辞書式順序で最小の順列を与える)、次に、次の順列が見つかる限り、次の順列に進むことを繰り返します。この方法は、14世紀のインドのナラヤナパンディタにまでさかのぼり、頻繁に再発見されています。[49]

次のアルゴリズムは、指定された順列の後に辞書式順序で次の順列を生成します。指定された順列をインプレースで変更します。

  1. a [ k ] < a [ k +1 ]となる最大のインデックスkを見つけます。そのようなインデックスが存在しない場合、順列は最後の順列です。
  2. a [ k ] < a [ l ]となるkより大きい最大のインデックスlを見つけます。
  3. a [ k ]の値[ l ]の値と交換します
  4. a [ k +1]から最後の要素a [ n ]までのシーケンスを逆にします

たとえば、シーケンス[1、2、3、4](昇順)があり、インデックスがゼロベースである場合、手順は次のとおりです。

  1. インデックスk =2。3は [ k +1]である4よりもまだ小さい最大のインデックスであるという条件を満たすインデックスに配置されるためです。
  2. インデックスl =3。これは、条件a [ k ] < a [ l ]を満たすために、シーケンス内で3より大きい唯一の値が4であるためです。
  3. [2]と[ 3]の値が交換されて、新しいシーケンス[1、2、4、3]が形成されます
  4. 最後の要素へのk -indexa [2]の後の順序が逆になりますこのインデックス(3)の後には1つの値しかないため、この場合、シーケンスは変更されません。したがって、初期状態の辞書式後継は並べ替えられます:[1、2、4、3]。

このアルゴリズムに従うと、次の辞書式順列は[1、3、2、4]になり、24番目の順列は[4、3、2、1]になり、その時点でa [ k ] < a [ k +1]が実行されます。存在せず、これが最後の順列であることを示します。

この方法では、順列ごとに約3つの比較と1.5のスワップを使用し、最初の並べ替えをカウントせずに、シーケンス全体で償却します。[50]

最小限の変更で生成

上記のアルゴリズムの代わりに、Steinhaus–Johnson–Trotterアルゴリズムは、2つの隣接する値を交換することにより、出力内の任意の2つの連続する順列が異なるという特性を使用して、特定のシーケンスのすべての順列に順序付けを生成します。順列に関するこの順序は、17世紀の英国のベルリンガーに知られており、その中で「プレーンチェンジ」として知られていました。この方法の利点の1つは、ある順列から次の順列へのわずかな変更により、順列ごとに一定時間でメソッドを実装できることです。同じことが、他のすべての出力順列をスキップすることによって、順列ごとに一定時間で、偶数の順列のサブセットを簡単に生成することもできます。[49]

An alternative to Steinhaus–Johnson–Trotter is Heap's algorithm,[51] said by Robert Sedgewick in 1977 to be the fastest algorithm of generating permutations in applications.[48]

The following figure shows the output of all three aforementioned algorithms for generating all permutations of length , and of six additional algorithms described in the literature.

Ordering of all permutations of length generated by different algorithms. The permutations are color-coded, where   1,   2,   3,   4.[52]
  1. Lexicographic ordering;
  2. Steinhaus–Johnson–Trotter algorithm;
  3. Heap's algorithm;
  4. Ehrlich's star-transposition algorithm:[49] in each step, the first entry of the permutation is exchanged with a later entry;
  5. Zaks' prefix reversal algorithm:[53] in each step, a prefix of the current permutation is reversed to obtain the next permutation;
  6. Sawada-Williams' algorithm:[54] each permutation differs from the previous one either by a cyclic left-shift by one position, or an exchange of the first two entries;
  7. Corbett's algorithm:[55] each permutation differs from the previous one by a cyclic left-shift of some prefix by one position;
  8. Single-track ordering:[56] each column is a cyclic shift of the other columns;
  9. Single-track Gray code:[56] each column is a cyclic shift of the other columns, plus any two consecutive permutations differ only in one or two transpositions.

Meandric permutations

Meandric systems give rise to meandric permutations, a special subset of alternate permutations. An alternate permutation of the set {1, 2, ..., 2n} is a cyclic permutation (with no fixed points) such that the digits in the cyclic notation form alternate between odd and even integers. Meandric permutations are useful in the analysis of RNA secondary structure. Not all alternate permutations are meandric. A modification of Heap's algorithm has been used to generate all alternate permutations of order n (that is, of length 2n) without generating all (2n)! permutations.[57][unreliable source?] Generation of these alternate permutations is needed before they are analyzed to determine if they are meandric or not.

The algorithm is recursive. The following table exhibits a step in the procedure. In the previous step, all alternate permutations of length 5 have been generated. Three copies of each of these have a "6" added to the right end, and then a different transposition involving this last entry and a previous entry in an even position is applied (including the identity; that is, no transposition).

Previous sets Transposition of digits Alternate permutations
1-2-3-4-5-6 1-2-3-4-5-6
4, 6 1-2-3-6-5-4
2, 6 1-6-3-4-5-2
1-2-5-4-3-6 1-2-5-4-3-6
4, 6 1-2-5-6-3-4
2, 6 1-6-5-4-3-2
1-4-3-2-5-6 1-4-3-2-5-6
2, 6 1-4-3-6-5-2
4, 6 1-6-3-2-5-4
1-4-5-2-3-6 1-4-5-2-3-6
2, 6 1-4-5-6-3-2
4, 6 1-6-5-2-3-4

Applications

Permutations are used in the interleaver component of the error detection and correction algorithms, such as turbo codes, for example 3GPP Long Term Evolution mobile telecommunication standard uses these ideas (see 3GPP technical specification 36.212[58]). Such applications raise the question of fast generation of permutations satisfying certain desirable properties. One of the methods is based on the permutation polynomials. Also as a base for optimal hashing in Unique Permutation Hashing.[59]

See also

Notes

  1. ^ The order is often implicitly understood. A set of integers is naturally written from smallest to largest; a set of letters is written in lexicographic order. For other sets, a natural order needs to be specified explicitly.
  2. ^ 1 is frequently used to represent the identity element in a non-commutative group
  3. ^ More precisely, variations without repetition. The term is still common in other languages and appears in modern English most often in translation.
  4. ^ The natural order in this example is the order of the letters in the original word.
  5. ^ In older texts circular permutation was sometimes used as a synonym for cyclic permutation, but this is no longer done. See Carmichael (1956, p. 7)

References

  1. ^ Webster (1969)
  2. ^ McCoy (1968, p. 152)
  3. ^ Nering (1970, p. 86)
  4. ^ Broemeling, Lyle D. (1 November 2011). "An Account of Early Statistical Inference in Arab Cryptology". The American Statistician. 65 (4): 255–257. doi:10.1198/tas.2011.10191. S2CID 123537702.
  5. ^ Biggs, N. L. (1979). "The Roots of Combinatorics". Historia Math. 6 (2): 109–136. doi:10.1016/0315-0860(79)90074-0.
  6. ^ Stedman 1677, p. 4.
  7. ^ Stedman 1677, p. 5.
  8. ^ Stedman 1677, pp. 6–7.
  9. ^ Stedman 1677, p. 8.
  10. ^ Stedman 1677, pp. 13–18.
  11. ^ "Combinations and Permutations". www.mathsisfun.com. Retrieved 2020-09-10.
  12. ^ Weisstein, Eric W. "Permutation". mathworld.wolfram.com. Retrieved 2020-09-10.
  13. ^ Scheinerman, Edward A. (March 5, 2012). "Chapter 5: Functions". Mathematics: A Discrete Introduction (3rd ed.). Cengage Learning. p. 188. ISBN 978-0840049421. Archived from the original on February 5, 2020. Retrieved February 5, 2020. It is customary to use lowercase Greek letters (especially π, σ, and τ) to stand for permutations.
  14. ^ Cameron 1994, p. 29, footnote 3.
  15. ^ Wussing, Hans (2007), The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory, Courier Dover Publications, p. 94, ISBN 9780486458687, Cauchy used his permutation notation—in which the arrangements are written one below the other and both are enclosed in parentheses—for the first time in 1815.
  16. ^ Bogart 1990, p. 17
  17. ^ Gerstein 1987, p. 217
  18. ^ a b Aigner, Martin (2007). A Course in Enumeration. Springer GTM 238. pp. 24–25. ISBN 978-3-540-39035-0.
  19. ^ Hall 1959, p. 54
  20. ^ Rotman 2002, p. 41
  21. ^ Bogart 1990, p. 487
  22. ^ Bona 2012, p.87 [Note that the book has a typo/error here, as it gives (45) instead of (54).]
  23. ^ a b Stanley, Richard P. (2012). Enumerative Combinatorics: Volume I, Second Edition. Cambridge University Press. p. 23. ISBN 978-1-107-01542-5.
  24. ^ Kitaev, Sergey (2011). Patterns in Permutations and Words. Springer Science & Business Media. p. 119. ISBN 978-3-642-17333-2.
  25. ^ Biggs, Norman L.; White, A. T. (1979). Permutation groups and combinatorial structures. Cambridge University Press. ISBN 978-0-521-22287-7.
  26. ^ Dixon, John D.; Mortimer, Brian (1996). Permutation Groups. Springer. ISBN 978-0-387-94599-6.
  27. ^ Cameron, Peter J. (1999). Permutation groups. Cambridge University Press. ISBN 978-0-521-65302-2.
  28. ^ Jerrum, M. (1986). "A compact representation of permutation groups". J. Algorithms. 7 (1): 60–78. doi:10.1016/0196-6774(86)90038-6. S2CID 18896625.
  29. ^ Charalambides, Ch A. (2002). Enumerative Combinatorics. CRC Press. p. 42. ISBN 978-1-58488-290-9.
  30. ^ Brualdi 2010, p. 46, Theorem 2.4.2
  31. ^ Brualdi 2010, p. 47
  32. ^ Brualdi 2010, p. 39
  33. ^ Bona 2012, pp. 97–103.
  34. ^ Sagan, Bruce (2001), The Symmetric Group (2 ed.), Springer, p. 3
  35. ^ Humphreys 1996, p. 84.
  36. ^ Hall 1959, p. 60
  37. ^ a b c Bona 2012, pp. 109–110.
  38. ^ Bóna 2004, p. 4f.
  39. ^ Bona 2012, pp. 4–5.
  40. ^ Bona 2012, p. 25.
  41. ^ Slocum, Jerry; Weisstein, Eric W. (1999). "15 – puzzle". MathWorld. Wolfram Research, Inc. Retrieved October 4, 2014.
  42. ^ Bóna 2004, p. 43.
  43. ^ Bóna 2004, pp. 43ff.
  44. ^ Knuth 1973, p. 12.
  45. ^ H. A. Rothe, Sammlung combinatorisch-analytischer Abhandlungen 2 (Leipzig, 1800), 263–305. Cited in Knuth 1973, p. 14
  46. ^ Fisher, R.A.; Yates, F. (1948) [1938]. Statistical tables for biological, agricultural and medical research (3rd ed.). London: Oliver & Boyd. pp. 26–27. OCLC 14222135.
  47. ^ Bacher, A.; Bodini, O.; Hwang, H.K.; Tsai, T.H. (2017). "Generating Random Permutations by Coin Tossing: Classical Algorithms, New Analysis, and Modern Implementation" (ACM Trans. Algorithms 13(2): 24:1–24:43 ed.). pp. 24–43.
  48. ^ a b Sedgewick, R (1977). "Permutation generation methods" (PDF). Computing Surveys. 9 (2): 137–164. doi:10.1145/356689.356692. S2CID 12139332.
  49. ^ a b c Knuth 2005, pp. 1–26.
  50. ^ "std::next_permutation". cppreference.com. 4 December 2017. Retrieved 31 March 2018.
  51. ^ Heap, B. R. (1963). "Permutations by Interchanges". The Computer Journal. 6 (3): 293–298. doi:10.1093/comjnl/6.3.293.
  52. ^ Mütze, Torsten; Sawada, Joe; Williams, Aaron. "Generate permutations". Combinatorial Object Server. Retrieved May 29, 2019.
  53. ^ Zaks, S. (1984). "A new algorithm for generation of permutations". BIT Numerical Mathematics. 24 (2): 196–204. doi:10.1007/BF01937486. S2CID 30234652.
  54. ^ Sawada, Joe; Williams, Aaron (2018). "A Hamilton path for the sigma-tau problem". Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. New Orleans, Louisiana: Society for Industrial and Applied Mathematics (SIAM). pp. 568–575. doi:10.1137/1.9781611975031.37.
  55. ^ Corbett, P. F. (1992). "Rotator graphs: An efficient topology for point-to-point multiprocessor networks". IEEE Transactions on Parallel and Distributed Systems. 3 (5): 622–626. doi:10.1109/71.159045.
  56. ^ a b Arndt, Jörg (2011). Matters Computational. Ideas, Algorithms, Source Code. Springer. doi:10.1007/978-3-642-14764-7. ISBN 978-3-642-14763-0.
  57. ^ Alexiou, A.; Psiha, M.; Vlamos, P. (2011). "Combinatorial permutation based algorithm for representation of closed RNA secondary structures". Bioinformation. 7 (2): 91–95. doi:10.6026/97320630007091. PMC 3174042. PMID 21938211.
  58. ^ "3GPP TS 36.212".
  59. ^ Dolev, Shlomi; Lahiani, Limor; Haviv, Yinnon (2013). "Unique permutation hashing". Theoretical Computer Science. 475: 59–65. doi:10.1016/j.tcs.2012.12.047.

Bibliography

Further reading

  • Biggs, Norman L. (2002), Discrete Mathematics (2nd ed.), Oxford University Press, ISBN 978-0-19-850717-8
  • Foata, Dominique; Schutzenberger, Marcel-Paul (1970), Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Mathematics, vol. 138, Berlin, Heidelberg: Springer-Verlag, ISBN 978-3-540-04927-2. The link is to a freely available retyped (LaTeX'ed) and revised version of the text originally published by Springer-Verlag.
  • Knuth, Donald (1998), Sorting and Searching, The Art of Computer Programming, vol. 3 (Second ed.), Addison–Wesley, ISBN 978-0-201-89685-5. Section 5.1: Combinatorial Properties of Permutations, pp. 11–72.
  • Sedgewick, Robert (1977). "Permutation generation methods". ACM Computing Surveys. 9 (2): 137–164. doi:10.1145/356689.356692. S2CID 12139332.
  • Masato, Kobayashi (2011). "Enumeration of bigrassmannian permutations below a permutation in Bruhat order". Order. 1: 131–137.


External links