順列

順列の最初の意味によれば、6つの列のそれぞれは3つの異なるボールの異なる順列である。

数学では、集合の順列は次の 2 つの異なる意味のいずれかになります。

• メンバーを連続的または線形順序で配置すること、または
• 順序付けられた集合の線形順序を変更する行為またはプロセス。^[1]

最初の意味の例は、集合{1, 2, 3}の6つの順列（順序）です。組で書くと、(1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、(3, 2, 1)となります。文字がすべて異なる単語のアナグラムも順列です。元の単語では文字が既に順序付けられており、アナグラムによって文字の順序が変わります。有限集合の順列の研究は、組合せ論と群論における重要なテーマです。

順列は数学のほぼすべての分野と、その他多くの科学分野で用いられています。コンピュータサイエンスではソートアルゴリズムの解析に、量子物理学では粒子の状態の記述に、生物学ではRNA配列の記述に用いられています。

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

2 番目の意味によれば、集合 Sの順列はSからそれ自身への全単射として定義されます。 ^{[2] [3]}つまり、それはSからSへの関数であり、そのすべての要素は像値としてちょうど 1 回出現します。このような関数は、各要素iを対応する で置き換えたSの要素の並べ替えに相当します。たとえば、順列 (3, 1, 2) は、次のように定義される 関数に対応します 。集合のすべての並べ替えのコレクションは、その集合の対称群と呼ばれるグループを形成します。群演算は関数の合成(1 つの並べ替えを次々に実行) であり、その結果、別の関数 (並べ替え) が生成されます。${\displaystyle \sigma :S\to S}$ ${\displaystyle \sigma (i)}$ ${\displaystyle \sigma }$ $${\displaystyle \sigma (1)=3,\quad \sigma (2)=1,\quad \sigma (3)=2.}$$

初等組合せ論において、k順列（k -permutations）あるいは部分順列（partial permutations ）とは、集合からk個の異なる要素を順序付けて並べたものである。kが集合の大きさに等しい場合、これらは前述の意味での順列である。

1974 年にエルネー・ルービックが発明した人気のパズル「ルービック キューブ」では、パズルの面を 1 回転させるごとに表面の色の順列が生成されます。

歴史

六十四卦と呼ばれる順列のようなものは、紀元前 1000 年頃にはすでに中国の易経(ピンイン: 易経) で使用されていました。

ギリシャでは、プルタルコスはカルケドン公クセノクラテス（紀元前396～314年）がギリシャ語の音節の数を発見したと記している。これは、順列と組み合わせに関する難問を解こうとした、記録に残る最初の試みであったと考えられる。^[4]

アラブの数学者であり暗号学者でもあったアル＝ハリール（717–786）は、『暗号文集』を著した。この本には、順列と組み合わせを初めて用いて、母音の有無を問わずあらゆるアラビア語の単語を列挙している。^[5]

n個の物体の順列の数を決定する規則は、西暦1150年頃にインド文化で知られていました。インドの数学者バースカラ2世の『リラーヴァティ』には、次のように訳される一節があります。

1から始まり1ずつ増加し、桁数まで続く等差数列の乗算の積は、特定の数字を持つ数のバリエーションになります。^[6]

1677年、ファビアン・ステッドマンは、チェンジリンギングにおける鐘の順列の数を説明する際に階乗について述べた。2つの鐘から始め、「まず、2つは2通りの方法で変化することが認められなければならない」と述べ、1 2と2 1を例に挙げて説明した。^[7] 次に、3つの鐘の場合、「3つから3倍の2つの数字が生成される」と説明し、これもまた例証されている。彼の説明は、「3を捨てれば1.2が残り、2を捨てれば1.3が残り、1を捨てれば2.3が残る」というものである。^[8] 次に、4つの鐘に移り、「捨てる」という議論を繰り返し、3つの鐘の組み合わせが4通りあることを示している。これは実質的に再帰的なプロセスである。彼は5つの鐘についても「捨てる」という手法を用い、結果として得られる120通りの組み合わせを表にまとめた。^[9] ここで彼は諦め、次のように述べている。

これらの方法の性質は、一つの数の変化がそれより小さな数の変化を全て包含するというものである。…一つの数の変化の完全な音は、それより小さな数の変化の完全な音を一つの全体に統合することによって形成されるように見える。^[10]

ステッドマンは順列の考察を広げ、アルファベットの文字の順列の数と20頭の馬小屋の馬の順列の数を考察している。^[11]

一見無関係に見える数学の問題が順列を用いて研究された最初の事例は、1770年頃にジョゼフ・ルイ・ラグランジュが多項式方程式の研究において、方程式の根の順列の性質が方程式を解く可能性と関連していることに気づいたときでした。この研究の流れは最終的に、エヴァリスト・ガロワの研究を通じてガロア理論に結実し、ガロア理論は、根号を用いて（未知数が1つの）多項式方程式を解くことに関して、何が可能で何が不可能かを包括的に記述しました。現代数学にも、問題を理解するために、それに関連する特定の順列の研究が必要となる同様の状況が数多くあります。

n 個の要素の置換としての順列の研究は、コーシー(1815 年の回想録) の著作を通じて、代数構造としての群の概念につながりました。

順列は、第二次世界大戦中にナチス・ドイツが使用した暗号装置であるエニグマの解読において重要な役割を果たしました。特に、順列の重要な性質の一つ、すなわち、2つの順列が同じサイクルタイプを持つ場合、それらは共役であるという性質は、暗号学者マリアン・レイェフスキによって1932年から1933年にかけてドイツのエニグマ暗号を解読するために利用されました。^{[12] [13]}

意味

数学の教科書では、順列を小文字のギリシャ文字で表記するのが慣例となっている。^[14]

順列は集合Sからそれ自身への全単射（可逆写像、一対一かつ全射関数）として定義できる。 恒等順列はすべての要素に対して定義され、数、あるいは単一の1サイクル（x）で表すことができる。^{[ 15] [16]}$${\displaystyle \sigma :S\ {\stackrel {\sim }{\longrightarrow }}\ S.}$$ ${\displaystyle \sigma (x)=x}$ ${\displaystyle x\in S}$ ${\displaystyle 1}$ ${\displaystyle {\text{id}}={\text{id}}_{S}}$

n個の元を持つ集合のすべての順列の集合は対称群 を形成し、群演算は関数 の合成である。したがって、群 内の2 つの順列と に対して、それらの積は で定義される 。合成は通常、ドットなどの記号なしで表記される。一般に、2 つの順列の合成は可換で はない。つまり、通常、順列と は等しくない。 ${\displaystyle S_{n}}$ ${\displaystyle \sigma }$ ${\displaystyle \tau}$ ${\displaystyle S_{n}}$ ${\displaystyle \pi =\sigma \tau }$ $${\displaystyle \pi (i)=\sigma (\tau (i)).}$$ ${\displaystyle \tau \sigma }$ ${\displaystyle \sigma \tau}$

集合からそれ自身への一対一である順列は、集合の並べ替えを実行する関数であり、能動順列または置換と呼ばれます。より古い観点では、順列はSのすべての要素の順序付けられた配置またはリストであり、受動順列と呼ばれます。^[17]この定義によれば、§ 1 行表記のすべての順列は受動的です。この意味は、能動変換と受動変換などにおける受動的な (つまり) 使用法^{[18] [19]}とは微妙に異なります。これらの使用法では、すべての順列は受動的な解釈が可能であるとみなされます (1 行表記、2 行表記などに関係なく)。

順列は、集合Sに作用する巡回群の軌道である、 1つ以上の互いに素な閉路に分解できます。閉路は、 の元に順列を繰り返し適用することで得られます。ここで を仮定します。k 個の元からなる閉路はk閉​​路と呼ばれます。(以下の § 閉路記法を参照) ${\displaystyle \sigma }$ ${\displaystyle \langle \sigma \rangle =\{1,\sigma ,\sigma ^{2},\ldots \}}$ ${\displaystyle x,\sigma (x),\sigma (\sigma (x)),\ldots ,\sigma ^{k-1}(x)}$ ${\displaystyle \sigma^{k}(x)=x}$

順列の不動点とは、xがそれ自身に取り込まれる、つまり1 サイクル を形成する順列のことである。不動点のない順列は、乱れと呼ばれる。2 つの要素（単一の 2 サイクル）を交換し、他の要素を固定する順列は、転置と呼ばれる。 ${\displaystyle \sigma }$ ${\displaystyle \sigma (x)=x}$ ${\displaystyle (\,x\,)}$

表記

順列を簡便に表すために、いくつかの表記法が広く用いられています。順列の性質は、順列化される要素の性質ではなく、その個数のみに依存するため、標準集合がしばしば用いられます。 サイクル表記法は簡潔で順列の構造を明確に示すため、よく用いられます。この記事では、特に断りのない限り、サイクル表記法を使用します。 ${\displaystyle \{1,2,\ldots ,n\}}$

2行表記

コーシーの2行表記法^{[20] [21]では、} Sの元を1行目に、その下の各元の像を2行目に列挙する。例えば、S = {1, 2, 3, 4, 5, 6}の順列は、関数

${\displaystyle \sigma (1)=2,\ \ \sigma (2)=6,\ \ \sigma (3)=5,\ \ \sigma (4)=4,\ \ \sigma (5)=3,\ \ \sigma (6)=1}$

次のように書くことができる

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5&6\\2&6&5&4&3&1\end{pmatrix}}.}$

Sの要素は最初の行に任意の順序で現れる可能性があるので、この順列は次のようにも書けます。

${\displaystyle \sigma ={\begin{pmatrix}2&3&4&5&6&1\\6&5&4&3&1&2\end{pmatrix}}={\begin{pmatrix}6&5&4&3&2&1\\1&3&4&5&6&2\end{pmatrix}}.}$

1行表記

Sの要素に「自然な」順序がある場合、^[b]とすると、2行表記の最初の行にこれを使います。 ${\displaystyle x_{1},x_{2},\ldots,x_{n}}$

${\displaystyle \sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}.}$

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

${\displaystyle \sigma =\sigma (x_{1})\;\sigma (x_{2})\;\sigma (x_{3})\;\cdots \;\sigma (x_{n})}$ 、

すなわち、 Sの要素を順序付けて並べたものである。^{[22] [23]} 1行表記と後述する循環表記を区別するために注意が必要である。一般的な用法としては、1行表記では括弧などの囲み記号を省略し、循環表記では括弧を使用する。1行表記は単語表現とも呼ばれる。^[24]

上記の例は次のようになります。

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5&6\\2&6&5&4&3&1\end{pmatrix}}=265431.}$

(エントリの一部に 2 桁以上の数字がある場合のみ、コンマを使用してこれらのエントリを区切るのが一般的です。)

このコンパクトな形式は、初等的な組合せ論やコンピュータサイエンスにおいてよく用いられます。特に、辞書式順序を用いて順列の大きさを比較する必要があるアプリケーションで有用です。

サイクル表記

サイクル記法は、集合Sの要素に順列を繰り返し適用した際の効果を記述する記法であり、軌道はサイクルと呼ばれます。順列はサイクルのリストとして記述されます。異なるサイクルは互いに素な要素の集合を含むため、これは「互いに素なサイクルへの分解」と呼ばれます。

順列を循環記法で 書き表すには、次のようにします。${\displaystyle \sigma }$

1. 開き括弧に続けて任意の要素x を書きます。 ${\displaystyle S}$ ${\displaystyle (\,x}$
2. xの軌道をトレースし、 を連続的に適用したときの値を書き記します。${\displaystyle \sigma }$ ${\displaystyle (\,x,\sigma (x),\sigma (\sigma (x)),\ldots }$
3. 値がx に戻るまで繰り返し、x を繰り返さずに括弧を閉じます。${\displaystyle (\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)}$
4. まだ書き込まれていないSの要素yを続けて、上記のプロセスを繰り返します。${\displaystyle (\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)(\,y\,\ldots \,)}$
5. Sのすべての要素が循環的に書き込まれるまで繰り返します。

また、1サイクルは推論できるため省略するのが一般的です。Sのどのサイクルにも現れない任意の要素xについては、暗黙的に と仮定します。[ 25 ^]${\displaystyle \sigma (x)=x}$

1-サイクルを省略するという慣例に従えば、個々のサイクルは、サイクルに含まれないすべての要素を固定する順列（長さが1より大きいサイクルが1つだけ存在する巡回順列）として解釈できる。この場合、互いに素なサイクルのリストは、これらの巡回順列の合成として見ることができる。例えば、1行順列はサイクル記法で次のように表すことができる。${\displaystyle \sigma =265431}$

${\displaystyle \sigma =(126)(35)(4)=(126)(35)。}$

これは巡回順列の合成として見ることができます。${\displaystyle \sigma =\kappa _{1}\kappa _{2}}$

${\displaystyle \kappa_{1}=(126)=(126)(3)(4)(5),\quad \kappa_{2}=(35)=(35)(1)(2)(6).}$

一般に順列は交換可能ではありませんが、分離したサイクルは交換可能です。たとえば、

${\displaystyle \sigma =(126)(35)=(35)(126)。}$

また、各サイクルは異なる開始点から書き換えることもできます。たとえば、

${\displaystyle \sigma =(126)(35)=(261)(53)。}$

このように、与えられた順列の互いに素な循環は、様々な方法で表記することができます。循環記法の便利な点は、順列の反転は各循環の要素の順序を逆にすることで表せることです。例えば、

${\displaystyle \sigma^{-1}=\left({\vphantom {A^{2}}}(126)(35)\right)^{-1}=(621)(53).}$

標準サイクル記法

組み合わせ論的な文脈によっては、サイクル内の要素や（互いに素な）サイクル自体の要素の順序を固定することが有用な場合があります。ミクローシュ・ボナは、以下の順序付けを標準サイクル記法と呼んでいます。

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

例えば、は標準循環記法におけるの順列である。^[26]$${\displaystyle (513)(6)(827)(94)}$$ ${\displaystyle S=\{1,2,\ldots ,9\}}$

リチャード・スタンレーはこれを順列の「標準表現」と呼び^[27]、マーティン・アイグナーは「標準形式」と呼んでいる^{[24] 。} セルゲイ・キタエフも「標準形式」という用語を使用しているが、両者の選択は逆である。つまり、各サイクルは最小元を最初にリストし、サイクルは最小元の降順で並べられている。^[28]

順列の合成

2つの順列の合成を表す方法は2つあります。最も一般的な表記法では、は任意の要素xを に写す関数です。 引数は関数の右側に記述されるため、 最も右側の順列は最初に引数に適用されます^{[29] 。}${\displaystyle \sigma \cdot \tau }$ ${\displaystyle \sigma (\tau (x))}$

順列の乗算に関する別の規則は、関数の左側に引数を書き、最も左側の順列が最初に作用するようにすることから来ています。^{[30] [31] [32]} この記法では、順列は指数として書かれることが多く、σがxに作用する場合はxσ^と書き、積はで定義されます。この記事では、右端の順列が最初に適用される最初の定義を使用します。 ${\displaystyle x^{\sigma \cdot \tau }=(x^{\sigma })^{\tau }}$

関数合成演算は群の公理を満たす。これは結合的であり、 を意味し、2つ以上の置換の積は通常括弧なしで表記される。合成演算には恒等元（恒等置換）も存在し、各置換には の逆関数（逆関数）が存在する。 ${\displaystyle (\rho \sigma )\tau =\rho (\sigma \tau )}$ ${\displaystyle {\text{id}}}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma ^{-1}}$ ${\displaystyle \sigma ^{-1}\sigma =\sigma \sigma ^{-1}={\text{id}}}$

この用語の他の用法順列

順序付けられた配列としての順列の概念には、特に古い文献において順列と呼ばれてきたいくつかの一般化が認められています。

け-順列n

古い文献や初等教科書では、nのk順列（部分順列、繰り返しのないシーケンス、変化、配置と呼ばれることもある）は、 n集合のk要素サブセットの順序付けられた配置（リスト）を意味します。^{[c] [33] [34]このような}k順列（k配置）の数は、、、、、、 などの記号で様々に表されます。[ 35 ^]は、次の式で計算されます。^[36]${\displaystyle n}$ ${\displaystyle P_{k}^{n}}$ ${\displaystyle _{n}P_{k}}$ ${\displaystyle ^{n}\!P_{k}}$ ${\displaystyle P_{n,k}}$ ${\displaystyle P(n,k)}$ ${\displaystyle A_{n}^{k}}$

${\displaystyle P(n,k)=\underbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} _{k\ \mathrm {因子} }}$ 、

これはk > nのときは0 、そうでない場合は

${\displaystyle {\frac {n!}{(nk)!}}.}$

積は、 が非負の整数であるという仮定なしに明確に定義され、組合せ論以外でも重要である。これはポッホハマー記号または階乗降階乗として知られている。${\displaystyle n}$ ${\displaystyle (n)_{k}}$ ${\displaystyle k}$ ${\displaystyle n^{\underline {k}}}$

${\displaystyle P(n,k)={_{n}}P_{k}=(n)_{k}=n^{\underline {k}}.}$

この「順列」という用語の用法は、「組み合わせ」という用語と密接に関連しており、部分集合を意味します。集合Sのk 組み合わせは、 Sのk要素部分集合です。つまり、組み合わせの要素は順序付けられていません。Sのk組み合わせをあらゆる方法で順序付けると、 Sのk順列が生成されます。したがって、 n集合のk組み合わせの数C ( n , k ) は、 nのk順列の数と次の関係があります。

${\displaystyle C(n,k)={\frac {P(n,k)}{P(k,k)}}={\frac {n^{\underline {k}}}{k!}}={\frac {n!}{(nk)!\,k!}}.}$

これらの数値は二項係数 とも呼ばれ、通常は次のように表記されます。${\displaystyle {\tbinom {n}{k}}}$

${\displaystyle C(n,k)={_{n}}C_{k}={\binom {n}{k}}.}$

繰り返しによる順列

集合Sのk個の要素を順序付けて並べたもので、繰り返しが許されているものはk組と呼ばれます。これは通常の意味での順列ではありませんが、繰り返しを含む順列と呼ばれることもあります。また、アルファベットS上の単語や文字列とも呼ばれます。集合S がn個の要素を持つ場合、 S上のk組の数は${\displaystyle n^{k}.}$

多重集合の順列

左側に繰り返しがなく、右側に繰り返しがある順列

Mが有限多重集合である場合、多重集合順列とは、 Mの要素を順序付けて並べたもので、各要素がMにおけるその多重度とちょうど同じ回数出現する配列である。ある単語のアナグラムで、ある文字が繰り返される例は、多重集合順列の例である。^[d] Mの要素の多重度（ある順序で）が、、… であり、それらの合計（つまり、Mのサイズ）がnである場合、 Mの多重集合順列の数は多項式係数で与えられる。^[37]${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$ ${\displaystyle m_{l}}$

${\displaystyle {n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}={\frac {\left(\sum _{i=1}^{l}{m_{i}}\right)!}{\prod _{i=1}^{l}{m_{i}!}}}.}$

例えば、MISSISSIPPIという単語の異なるアナグラムの数は次のとおりです。^[38]

${\displaystyle {\frac {11!}{1!\,4!\,4!\,2!}}=34650}$ 。

多重集合Mのk順列は、 Mのk要素のシーケンスであり、各要素はMでの多重度(要素の繰り返し数) 以下の回数だけ出現します。

循環順列

順列は、配置として捉えられる場合、線状配置と呼ばれることがあります。しかし、オブジェクトが円形に配置されている場合、この明確な順序付けは弱まります。配置には「最初の要素」は存在せず、どの要素も開始点とみなせるからです。異なるオブジェクトを円形に配置することを円順列と呼びます。^{[39] [e]これらは、線状配置の最後の要素を先頭に移動することで生成される}同値関係に基づき、これらのオブジェクトの通常の順列の同値類として正式に定義できます。

2つの円順列は、一方を他方に回転させることができる場合、等価です。次の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個の要素 を持つ集合には( n – 1)! 通りの円順列が存在します。

プロパティ

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

k個の互いに素な閉路を持つn順列の数は第一種符号なしスターリング数であり、またはで表される。^[40]${\displaystyle c(n,k)}$ ${\displaystyle [{\begin{smallmatrix}n\\k\end{smallmatrix}}]}$

サイクルタイプ

n個の要素を持つ集合の順列の循環（不動点を含む）は、その集合を分割する。したがって、これらの循環の長さはnの整数分割を形成し、これはの循環型（あるいは循環構造、循環形状）と呼ばれる。循環型には、 のすべての不動点に対して「1」が、すべての転置に対して「2」が、といった具合である。 の循環型は、${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \beta =(1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)}$ ${\displaystyle (3,2,2,1).}$

これはより簡潔な形で[1 ¹ 2 ² 3 ¹ ]と書くこともできる。より正確には、一般形は であり、それぞれの長さの閉路の数である。与えられた閉路型における順列の数は^{[41]である。}${\displaystyle [1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}]}$ ${\displaystyle \alpha _{1},\ldots ,\alpha _{n}}$

${\displaystyle {\frac {n!}{1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}\alpha _{1}!\alpha _{2}!\dotsm \alpha _{n}!}}}$ 。

n個の要素を持つ集合の循環タイプの数は、パーティション関数 の値に等しくなります。 ${\displaystyle p(n)}$

Polyaのサイクル インデックス多項式は、順列をそのサイクル タイプごとにカウントする 生成関数です。

順列活用

一般に、サイクル表記法で書かれた合成順列は、簡単に記述できるパターンには従いません。合成される順列のサイクルは、合成される順列のサイクルとは異なる場合があります。しかし、サイクル型は、ある順列を別の順列 で共役させる特殊なケース、つまり積 を形成する場合には保存されます。ここで、は によるの共役であり、そのサイクル表記法は、 のサイクル表記法を取り、 をそのすべての要素に適用することで得られます。 ^[42]したがって、2つの順列が同じサイクル型を持つ場合、それらはまさに共役です。 ${\displaystyle \sigma }$ ${\displaystyle \pi }$ ${\displaystyle \pi \sigma \pi ^{-1}}$ ${\displaystyle \pi \sigma \pi ^{-1}}$ ${\displaystyle \sigma }$ ${\displaystyle \pi }$ ${\displaystyle \sigma }$ ${\displaystyle \pi }$

順列の順序

順列の位数は、となる最小の正の整数mです。これは、その循環の長さの最小公倍数です。例えば、 の位数はです。 ${\displaystyle \sigma }$ ${\displaystyle \sigma ^{m}=\mathrm {id} }$ ${\displaystyle \sigma =(152)(34)}$ ${\displaystyle {\text{lcm}}(3,2)=6}$

順列の偶奇性

有限集合のあらゆる順列は、転置の積として表すことができます。^[43] 与えられた順列に対してこのような表現が多数存在する場合もありますが、それらはすべて転置の数が偶数か奇数かのどちらかです。したがって、すべての順列は、この数に応じて 偶数または奇数に分類できます。

この結果は、各順列に符号（ と表記）を割り当てるように拡張できる。が偶数の場合、 が奇数の場合である。すると、2つの順列と${\displaystyle \operatorname {sgn} \sigma }$ ${\displaystyle \operatorname {sgn} \sigma =+1}$ ${\displaystyle \sigma }$ ${\displaystyle \operatorname {sgn} \sigma =-1}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \pi }$

${\displaystyle \operatorname {sgn} (\sigma \pi )=\operatorname {sgn} \sigma \cdot \operatorname {sgn} \pi .}$

すると、${\displaystyle \operatorname {sgn} \left(\sigma \sigma ^{-1}\right)=+1.}$

順列の符号は、その順列行列の行列式に等しくなります(下記)。

行列表現

順列行列は、各列と各行にちょうど 1 の要素があり、他のすべての要素は 0 であるn × n行列です。順列行列を {1, 2, ..., n } の順列に割り当てる方法はいくつかあります。1 つの自然な方法は、 をの線形変換として定義し、その標準基底を で置換し、 をその行列として定義することです。つまり、のj^番目の列は n × 1 の列ベクトルに等しくなります。その ( i , j ) 要素は、 i = σ ( j )の場合は 1 になり、それ以外の場合は 0 になります。線形写像の合成は行列の乗算によって記述されるため、この構成は順列の合成と互換性があります。${\displaystyle L_{\sigma}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \{\mathbf {e} _{1},\ldots ,\mathbf {e} _{n}\}}$ ${\displaystyle L_{\sigma }(\mathbf {e} _{j})=\mathbf {e} _{\sigma (j)}}$ ${\displaystyle M_{\sigma}}$ ${\displaystyle M_{\sigma}}$ ${\displaystyle \mathbf {e} _{\sigma (j)}}$

${\displaystyle M_{\sigma }M_{\tau }=M_{\sigma \tau }}$ 。

たとえば、1 行の順列には積があり、対応する行列は次のようになります。${\displaystyle \sigma =213,\ \tau =231}$ ${\displaystyle \sigma \tau =132}$ $${\displaystyle M_{\sigma }M_{\tau }={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}={\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}=M_{\sigma \tau }.}$$

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

文献では、逆の慣例も一般的です。つまり、置換σは、( i , j ) 要素がj = σ ( i ) の場合には 1 、それ以外の場合には 0 となる行列に関連付けられます。この慣例において、置換行列は置換とは逆の順序で乗算されます。つまり、 です。この対応関係において、置換行列は 標準行ベクトルの右側に作用します。${\displaystyle P_{\sigma}=(M_{\sigma})^{-1}=(M_{\sigma})^{T}}$ ${\displaystyle P_{\sigma }P_{\tau }=P_{\tau \sigma }}$ ${\displaystyle 1\times n}$ ${\displaystyle ({\bf {e}}_{i})^{T}}$ ${\displaystyle ({\bf {e}}_{i})^{T}P_{\sigma }=({\bf {e}}_{\sigma (i)})^{T}}$

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

全順序集合の順列

いくつかの応用では、置換される集合の要素同士を比較します。この場合、集合Sは任意の2つの要素を比較できるように全順序性を持つ必要があります。これらの応用では、通常の≤関係を持つ集合{1, 2, ..., n }が最も頻繁に使用されます。

順列を 1 行表記でシーケンスとして記述した場合、順列の多くの特性はSの全順序に直接関係します。 ${\displaystyle \sigma =\sigma (1)\sigma (2)\cdots \sigma (n)}$

登り、下り、走行、超過、記録

nの順列 σにおける 上昇とは、 i  <  nの任意の位置において、次の値が現在の値よりも大きい場合のことです。つまり、i が上昇となるのは、次の値がある場合です。例えば、順列 3452167 には、（位置）1、2、5、6 に上昇があります。 ${\displaystyle \sigma (i)<\sigma (i{+}1)}$

同様に、下降は の場合の位置i  <  nなので、の場合のすべてのiは上昇か下降のいずれかです。 ${\displaystyle \sigma (i)>\sigma (i{+}1)}$ ${\displaystyle 1\leq i<n}$

順列の昇順連は、どちらの端にも延長できない、空でない増加する連続部分列である。これは連続する上昇の最大列に対応する（後者は空である可能性がある。連続する2つの下降の間には、長さ1の昇順連が存在する）。対照的に、順列の増加部分列は必ずしも連続しているわけではない。これは、1行表記のいくつかの値を省略することによって得られる増加列である。例えば、順列2453167には、昇順連として245、3、167が含まれるが、増加部分列として2367が含まれる。

順列にk −1回の降下がある場合、それはk回の昇順 の結合でなければならない。 ^[44]

nからk回上昇する順列の数は（定義により）オイラー数である。これはまた、 nからk回下降する順列の数でもある。しかし、一部の研究者は、オイラー数をk 回上昇する順列の数、つまりk − 1回下降する順列の数と定義している。^[45]${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$ ${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$

順列σ ₁ σ ₂ ... σ _nの超過とは、σ _j > jを満たす添え字jのことである。不等式が厳密でない場合（すなわち、σ _j ≥ j）、jは弱い超過と呼ばれる。k回の超過を伴うn順列の数は、k回の降下を伴うn順列の数と一致する。^[46]

順列σのレコードまたは左から右への最大値は、すべてのj < iに対してσ ( j ) < σ ( i )となる要素iです。

フォアタの遷移補題

フォアタの基本一対一変換は、与えられた標準閉路形式を持つ順列σを、括弧を取り除いた同じ要素の列を持つ一行表記の順列に変換する。^{[27] [47]}例えば： ${\displaystyle f(\sigma )={\hat {\sigma }}}$ $${\displaystyle \sigma =(513)(6)(827)(94)={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\3&7&5&9&1&6&8&2&4\end{pmatrix}},}$$

$${\displaystyle {\hat {\sigma}}=513682794={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\5&1&3&6&8&2&7&9&4\end{pmatrix}}.}$$

ここで、 σの各標準サイクルの最初の要素は、のレコード（左から右への最大値）になります。 が与えられている場合、そのレコードを見つけ、括弧を挿入することで逆変換 を構築できます。上記の例のレコードに下線を引いてください。これにより、 σのサイクルを再構築できます。 ${\displaystyle {\hat {\sigma }}}$ ${\displaystyle {\hat {\sigma }}}$ ${\displaystyle \sigma =f^{-1}({\hat {\sigma }})}$ ${\displaystyle {\hat {\sigma }}={\underline {5}}\,1\,3\,{\underline {6}}\,{\underline {8}}\,2\,7\,{\underline {9}}\,4}$

次の表は、 S = {1, 2, 3}の 6 つの順列について、およびσを示しています。各辺の太字のテキストは、一対一表現で使用される表記を示しています。 については 1 行表記、 σについては標準循環表記です。 ${\displaystyle {\hat {\sigma }}}$ ${\displaystyle {\hat {\sigma }}}$

$${\displaystyle {\begin{array}{l|l}{\hat {\sigma }}=f(\sigma )&\sigma =f^{-1}({\hat {\sigma }})\\\hline \mathbf {123} =(\,1\,)(\,2\,)(\,3\,)&123=\mathbf {(\,1\,)(\,2\,)(\,3\,)} \\\mathbf {132} =(\,1\,)(\,3\,2\,)&132=\mathbf {(\,1\,)(\,3\,2\,)} \\\mathbf {213} =(\,2\,1\,)(\,3\,)&213=\mathbf {(\,2\,1\,)(\,3\,)} \\\mathbf {231} =(\,3\,1\,2\,)&321=\mathbf {(\,2\,)(\,3\,1\,)} \\\mathbf {312} =(\,3\,2\,1\,)&231=\mathbf {(\,3\,1\,2\,)} \\\mathbf {321} =(\,2\,)(\,3\,1\,)&312=\mathbf {(\,3\,2\,1\,)} \end{配列}}}$$ 最初の系として、ちょうどk 個のレコードを持つn順列 の数は、ちょうどk 個のサイクルを持つn順列の数に等しい。この最後の数は第一種の符号なしスターリング数である。さらに、Foata の写像は、k 個の弱い超過を持つn順列を、 k − 1個の上昇を持つn順列に変換する。^[47] たとえば、(2)(31) = 321 にはk = 2 個の弱い超過（インデックス 1 と 2）があるが、f (321) = 231にはk − 1 = 1 個の上昇（インデックス 1、つまり 2 から 3 へ） がある。${\displaystyle c(n,k)}$

反転

15パズルでは、マス目を昇順に並べることが目的です。反転回数が奇数である初期配置は解けません。^[48]

順列 σの反転とは、順列の要素が逆の順序になっている位置のペア（i、j）である。[ 49 ]したがって、^降下 とは隣接する2つの位置における反転である。例えば、σ = 23154では（i、j）=（1、3）、（2、3）、（4、5）となり、（σ（i）、σ（j））=（2、1）、（3、1）、（5、4）となる。 ${\displaystyle i<j}$ ${\displaystyle \sigma (i)>\sigma (j)}$

反転は値のペア（σ（i）、σ（j ））として定義されることがあります。これは反転の数には影響せず、逆のペア（σ（j）、σ（i ））は、逆順列σ ⁻¹に対する上記の意味での反転です。

反転の数は、順列の要素が順序どおりでない程度を測る重要な尺度であり、σとσ ^{−1について同じです。} k個の反転を持つ順列を順序どおりに整列させる(つまり、恒等順列に変換する) ことは、隣接する転置 を(右乗算で) 連続して適用することによって常に可能であり、 k回のそのような操作のシーケンスが必要です。さらに、隣接する転置については、任意の合理的な選択が機能します。各ステップで、 iとi + 1の転置を選択すれば十分です。ここで、 i は、これまでに修正された順列の降下です (そのため、転置により、この特定の降下は削除されますが、他の降下が作成される場合があります)。これは、このような転置を適用すると、反転の数が 1 減少するためです。この数が 0 でない限り、順列は恒等ではないため、少なくとも 1 つの降下があります。バブルソートと挿入ソートは、シーケンスを順序付けるこの手順の特殊な例として解釈できます。ちなみに、この手順は、任意の順列σが隣接する転置の積として表せることを証明しています。これは、σ を恒等転置に変換する任意の転置シーケンスを単純に反転すれば良いためです。実際、σ を恒等転置に変換するすべての隣接する転置シーケンスを列挙することで（反転後に）、σ を隣接する転置の積として 表す最小の長さの式すべての完全なリストが得られます。

nのk回の反転を伴う順列の数はマホーニアン数で表される。^[50]これは積の展開における 係数である。${\displaystyle q^{k}}$

$${\displaystyle [n]_{q}!=\prod _{m=1}^{n}\sum _{i=0}^{m-1}q^{i}=1\left(1+q\right)\left(1+q+q^{2}\right)\cdots \left(1+q+q^{2}+\cdots +q^{n-1}\right),}$$

表記はq階乗を表します。この展開はネックレスの研究ではよく見られます。 ${\displaystyle [n]_{q}!}$

と となるようなものとしよう。この場合、逆元 の重みはであるとする。小林（2011）は列挙公式 ${\displaystyle \sigma \in S_{n},i,j\in \{1,2,\dots ,n\}}$ ${\displaystyle i<j}$ ${\displaystyle \sigma (i)>\sigma (j)}$ ${\displaystyle (i,j)}$ ${\displaystyle \sigma (i)-\sigma (j)}$ $${\displaystyle \sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{はビグラスマン分布である}}\}}$$

ここで、 は対称群におけるブルハット順序を表す。この次数付き半順序は、コクセター群の文脈でしばしば現れる。 ${\displaystyle \leq }$

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

番号順列

n個のものの順列を表す 1 つの方法は、 0 ≤  N  <  n ! となる整数Nを使用することです。ただし、数値と、順列の表現を順序付けられた配列 (シーケンス) として変換する便利な方法が提供される必要があります。これは任意の順列の最もコンパクトな表現を与え、コンピューティングにおいては、nが十分小さくN をマシン ワードで保持できる場合に特に魅力的です。32 ビット ワードの場合、これはn  ≤ 12 を意味し、64 ビット ワードの場合、これはn  ≤ 20 を意味します。変換は、数値のシーケンスd _n、d _{n −1}、...、d ₂、d ₁の中間形式を介して実行できます。ここで、 d _iはi未満の負でない整数です( d ₁は常に 0 であるため省略できますが、これがあることで、後続の順列への変換の記述が容易になります)。最初のステップは、Nを階乗数法で表現することです。これは、n !未満の数の場合、連続する桁の基数（位取りまたは乗算係数）が( n −1)!、( n −2)!、...、2!、1!となる特定の混合基数表現です。2番目のステップでは、このシーケンスをLehmerコード、または（ほぼ等価的に）反転表として解釈します。

順列 σのレーマーコードにおいて、数d _{n は}最初の項σ ₁の選択を表し 、数d _{n −1}は残りのn − 1個の要素の中から2番目の項σ ₂の選択を表します 。以下同様です。より正確には、各d _{n +1− i}は項σ _iより小さい残りの要素の数を示します。これらの残りの要素は後の項σ _jとして必ず現れるため、数字d _{n +1− i は}i を小さい添え字とする反転( i , j )の数を表します( i  <  jかつσ _i  >  σ _jとなる値jの数)。σの 反転表も非常に似ていますが、ここではd _{n +1−} k_は反転 ( i , j )の数を表します。ここでk  =  σ _{j は}反転順に現れる2つの値のうち小さい方として現れます。^[51]

両方のエンコードは、n× n の ローテ図^[52]（ハインリヒ・アウグスト・ローテにちなんで名付けられた）で視覚化することができる。この図では、（i、σi）の点は順列のエントリを示し、（i、σj）の十字は反転（i、j ）を示す_。反転の定義により、その列_の点（j、σj）の前であり、かつその行の点（i、σi）の前にある正方形には十字が表示される_。レーマーコードは連続する行_の十字の数をリストし、反転表は連続する列の十字の数をリストする。これは逆順列のレーマーコードであり、その逆もまた同様である。

Lehmer コードd _n、d _{n −1}、 ...、d ₂、d ₁を順序付きセットSの順列に効果的に変換するには、 Sの要素を昇順で並べたリストから開始し、 iが1 からnまで増加する場合、 σ _{i を}、リスト内でその前にd _{n +1− i}個の他の要素がある要素に設定し、その要素をリストから削除します。 反転表d _n、d _{n −1}、 ...、d ₂、d _{1を対応する順列に変換するには、最初は空のシーケンスに}Sの要素を最大から最小の順に挿入しながら、d _1からd _nまでの数をトラバースします。反転表の数dを使用するステップでは、 Sの要素が、すでに存在するd個の要素が前に存在するポイントでシーケンスに挿入されます。あるいは、 n 個の空きスロットの行から始めて、反転表の数字とSの要素の両方を逆の順序で処理し、各ステップでSの要素を、他のd個の空きスロットが先行する空きスロットに配置することもできます。

連続する自然数を階乗数システムに変換すると、それらのシーケンスは辞書式順序で生成されます(混合基数システムの場合と同様)。さらにそれらを順列に変換すると、Lehmer コード解釈が使用されている場合は辞書式順序が保持されます (反転表を使用すると異なる順序が得られ、最初のエントリの値ではなく、エントリ 1 の場所によって順列を比較することから始めます)。階乗数システム表現の数の合計は、順列の反転の数を示し、その合計の偶奇は順列のシグネチャを示します。さらに、反転表のゼロの位置は、順列の左から右への最大値 (例では 6、8、9) を示しますが、Lehmer コード内のゼロの位置は、右から左への最小値 (例では、値 1、2、5 の 4、8、9 の位置) です。これにより、すべての順列における極値の分布を計算できます。Lehmerコードd _n , d _{n −1} , ..., d ₂ , d _{1を持つ順列には、} d _i ≥ d _{i +1}の場合にのみ、n − iの上昇があります。

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

計算において、与えられた値の列の順列を生成する必要が生じる場合があります。この処理に最適な手法は、ランダムに選択された順列をいくつか生成したいのか、それともすべての順列を生成するのか、そして後者の場合は特定の順序付けが必要かどうかによって異なります。また、与えられた列の要素間に等号が存在する可能性を考慮する必要があるかどうかも問題となります。等号が存在する場合、列の異なる多重集合順列のみを生成する必要があります。

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

順列のランダム生成

n個の値のシーケンスからランダムな順列を生成する場合、シーケンスにランダムに選択されたnの順列を適用するか、シーケンスの異なる順列（多重集合）の集合からランダムな要素を選択するかは関係ありません。これは、値が重複している場合、同じ順列になるnの異なる順列が多数存在する可能性があるとしても、各結果に対してそのような順列の数は等しくなるためです。n が大きくなると n ! の増加により不可能になる体系的な生成とは異なり、ランダム生成ではnが小さいと 仮定する理由はありません。

ランダムな順列を生成するための基本的な考え方は、0 ≤ d _i < i ( d ₁は常に 0 なので省略できる) を満たすn ! 個の整数シーケンスd ₁ , d ₂ ,..., d _nの 1 つをランダムに生成し、これを全単射対応によって順列に変換することである。後者の対応については、(逆) シーケンスを Lehmer コードとして解釈することができ、これによって、1938 年にRonald FisherとFrank Yatesによって初めて発表された生成方法が得られる。^[53] 当時はコンピュータ実装は問題ではなかったが、この方法は、上で概説したように、Lehmer コードから順列に効率的に変換するという困難を抱えている。これは、別の全単射対応を使用することで改善できる。つまり、d _iを使用してシーケンスの残りのi個の要素から要素を選択した後 ( iの値が減少するため)、要素を削除してさらに要素を 1 つ下げてシーケンスをコンパクト化するのではなく、その要素を最後に残った要素と交換するのである。したがって、選択対象となる残りの要素は、元のシーケンスと同じ順序で出現しない場合でも、各時点において連続した範囲を形成します。整数シーケンスから順列へのマッピングは多少複雑ですが、即時帰納法によって、各順列が正確に1つの方法で生成されることがわかります。選択された要素が最後に残った要素である場合、スワップ操作は省略できます。これは条件のテストを正当化するほど頻繁に発生するものではありませんが、すべての順列が生成できることを保証するためには、最後の要素が選択候補に含まれている必要があります。

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

 i がnから 2まで実行し、 d i ← { 0, ..., i − 1 }
    のランダムな要素を取り、 a [ d i ] とa [ i − 1]
を入れ替える 
     

これは次のように 配列の初期化と組み合わせることができる。a[i] = i

 i が0からn −1までの 場合、 d i +1 ← { 0, ..., i }
    のランダムな要素a [ i ] ← a [ d i +1 ]
     a [ d i +1 ] ← i
    

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

しかし、フィッシャー・イェーツ法は順列を生成するための最速のアルゴリズムではない。なぜなら、フィッシャー・イェーツ法は本質的に順次的なアルゴリズムであり、「分割統治」の手順で並列的に同じ結果を得ることができるからである。^[54]

辞書順生成

与えられたシーケンスのすべての順列を体系的に生成する方法は数多くある。^{[55]古典的で単純かつ柔軟なアルゴリズムの一つは、}辞書式順序 で次の順列が存在する場合にそれを見つけることに基づいている。このアルゴリズムは重複値を扱うことができ、重複値の場合は、異なる多重集合順列をそれぞれ一度ずつ生成する。通常の順列の場合でも、Lehmerコードの値を辞書式順序で生成し（階乗法を使用する可能性もある）、それを順列に変換するよりもはるかに効率的である。このアルゴリズムは、シーケンスを（弱く）昇順でソートすることから始め（辞書式順序で最小の順列を与える）、次に次の順列が見つかるまで繰り返して次の順列に進む。この手法は14世紀インドのナラヤナ・パンディタに遡り、頻繁に再発見されている。^[56]

以下のアルゴリズムは、与えられた順列の辞書順で次の順列を生成します。与えられた順列をその場で変更します。

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

たとえば、シーケンス [1, 2, 3, 4] (昇順) が与えられ、インデックスが0 から始まる場合、手順は次のようになります。

1. インデックスk = 2 です。これは、3 が、 a [ k + 1] である 4より小さい最大のインデックスであるという条件を満たすインデックスに配置されているためです。
2. インデックスl = 3 です。条件a [ k ] < a [ l ]を満たすために、シーケンス内で 3 より大きい値は 4 のみであるためです。
3. a [2]とa [3]の値が入れ替えられ、新しいシーケンス[1, 2, 4, 3]が形成されます。
4. kインデックスa [2]から最終要素までのシーケンスは反転されます。このインデックスの後に続く値は 1 つだけ（3）であるため、このインスタンスではシーケンスは変更されません。したがって、初期状態の辞書式順序は [1, 2, 4, 3] と入れ替わります。

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

この方法では、最初のソートを除いて、シーケンス全体にわたって償却される順列ごとに約3回の比較と1.5回の交換が使用されます。^[57]

最小限の変更による世代

上記のアルゴリズムの代替として、シュタインハウス・ジョンソン・トロッターアルゴリズムが提案されている。これは、与えられたシーケンスのすべての順列に順序付けを行い、その出力における任意の2つの連続する順列は、隣接する2つの値を入れ替えることによって異なるという性質を持つ。この順列の順序付けは17世紀のイギリスの鐘つき人に知られており、彼らはこれを「プレーン・チェンジズ」と呼んでいた。この手法の利点の一つは、順列間の変化が小さいため、順列ごとに定数時間で実装できることである。また、同じ手法を用いて、出力順列を1つおきにスキップすることで、偶数順列のサブセットも順列ごとに定数時間で容易に生成することができる。^[56]

スタインハウス・ジョンソン・トロッターの代替としてヒープアルゴリズム^[58]があり、これは1977年にロバート・セジウィックによってアプリケーションにおける順列生成の最速アルゴリズムと評された。^[55]

次の図は、長さ のすべての順列を生成するための前述の 3 つのアルゴリズムと、文献に記載されている 6 つの追加アルゴリズム の出力を示しています。${\displaystyle n=4}$

異なるアルゴリズムによって生成された長さのすべての順列の順序。順列は色分けされており、${\displaystyle n=4}$   1、  2、  3、  4. [ ^59]

1. 辞書式順序;
2. シュタインハウス・ジョンソン・トロッターアルゴリズム;
3. ヒープアルゴリズム;
4. エーリッヒのスター転置アルゴリズム：^[56]各ステップで、順列の最初のエントリが後のエントリと交換されます。
5. Zaksのプレフィックス反転アルゴリズム：^[60]各ステップで、現在の順列のプレフィックスを反転して次の順列を取得します。
6. 沢田・ウィリアムズのアルゴリズム: ^[61]各順列は、1つの位置の巡回左シフト、または最初の2つのエントリの交換によって前の順列と異なります。
7. コーベットのアルゴリズム: ^[62]各順列は、ある接頭辞を1つ左に循環シフトすることによって前の順列と異なります。
8. シングルトラック順序付け：^[63]各列は他の列の巡回シフトである。
9. シングルトラックグレイコード：^[63]各列は他の列の巡回シフトであり、任意の2つの連続する順列は1つまたは2つの転置のみが異なる。
10. ネストされたスワップを生成するアルゴリズムは、ネストされたサブグループに接続されたステップで構成されています。各順列は、前の順列から左への転置乗算によって得られます。このアルゴリズムは、インデックスの階乗法に接続されています。${\displaystyle S_{k}\subset S_{k+1}}$

ネストされたスワップステップにおける順列の生成

スワップ（転置、2サイクル）の明示的なシーケンスがここで説明されており、各スワップは（左側で）前のチェーンに適用され、新しい順列を提供するため、すべての順列をそれぞれ1回だけ取得できます。^[64]このカウント/生成手順には、ステップごとに与えられる追加の構造（ネストされていると呼ぶ）があります。 を完全に取得した後、後述するコセットの代表を適切に選択することにより、 のコセットによる取得を続行します。それぞれが順番に生成されるため、最後の要素があります。したがって、スワップによって生成した後、 における次の順列は、何らかの についてで ある必要があります。次に、生成されたすべてのスワップが 繰り返され、コセット 全体を生成し、そのコセット の最後の順列に到達します。次のスワップでは、順列を別のコセット の代表に移動する必要があります。 ${\displaystyle (pq)}$ ${\displaystyle S_{k-1}}$ ${\displaystyle S_{k}\backslash S_{k-1}}$ ${\displaystyle S_{k-1}\tau_{i}}$ ${\displaystyle S_{k-1}}$ ${\displaystyle S_{k}}$ ${\displaystyle \tau_{i}}$ ${\displaystyle S_{m}}$ ${\displaystyle \lambda _{m}\in S_{m}}$ ${\displaystyle S_{k-1}}$ ${\displaystyle S_{k}\backslash S_{k-1}}$ ${\displaystyle \tau _{1}=(p_{1}k)\lambda _{k-1}}$ ${\displaystyle 1\leq p_{1}$ ${\displaystyle S_{k-1}}$ ${\displaystyle S_{k-1}\tau_{1}}$ ${\displaystyle \lambda _{k-1}\tau _{1}}$ ${\displaystyle \tau _{2}=(p_{2}k)\lambda _{k-1}\tau _{1}}$

同じ方法を続けると、 の剰余類の 剰余類代表が得られる。順序付き集合( ) は剰余類開始集合と呼ばれる。これらの代表のうち2つが同じ剰余類に属するのは 、 の 場合に限り、すなわちである。結論として、順列がすべて異なる剰余類の代表となるのは、任意の に対して の場合に限り、である（繰り返し条件なし）。特に、生成されたすべての順列が異なっているために、値が異なっている必要はない。この過程で が得られ、これが再帰手順を提供する。 ${\displaystyle \tau_{j}=(p_{j}k)\lambda_{k-1}\cdots\lambda_{k-1}(p_{i}k)\lambda_{k-1}\cdots\lambda_{k-1}(p_{1}k)\lambda_{k-1}}$ ${\displaystyle S_{k-1}}$ ${\displaystyle S_{k}}$ ${\displaystyle (p_{1},\ldots,p_{k-1})}$ ${\displaystyle 0\leq p_{i}$ ${\displaystyle \tau _{j}(\tau _{i})^{-1}=(p_{j}k)\lambda _{k-1}(p_{j-1}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{i+1}k)=\varkappa _{ij}\in S_{k-1}}$ ${\displaystyle \varkappa _{ij}(k)=k}$ ${\displaystyle \tau _{i}\in S_{k}-S_{k-1}}$ ${\displaystyle k>j>i\geq 1}$ ${\displaystyle (\lambda _{k-1})^{ji}p_{i}\neq p_{j}}$ ${\displaystyle p_{i}}$ ${\displaystyle \lambda_{k}=\lambda_{k-1}(p_{k-1}k)\lambda_{k-1}(p_{k-2}k)\lambda_{k-1}\cdots \lambda_{k-1}(p_{1}k)\lambda_{k-1}}$

例: 明らかに、の場合、 が成り立ちます。 を構築するには、重複なし条件を満たす剰余類の始まりの 2 つの可能性しかありません。選択すると になります。 を生成し続けるには、適切な剰余類の始まり (重複なし条件を満たす) が必要です。 という便利な選択肢があり、 になります 。次に、剰余類の始まり (重複なし条件を満たす) の便利な選択肢を構築するには となり、 になります。 ${\displaystyle \lambda_{2}}$ ${\displaystyle \lambda _{2}=(12)}$ ${\displaystyle \lambda_{3}}$ ${\displaystyle p_{1}=p_{2}=1}$ ${\displaystyle \lambda_{3}=\lambda_{2}(13)\lambda_{2}(13)\lambda_{2}=(13)}$ ${\displaystyle S_{4}}$ ${\displaystyle p_{1}=1,p_{2}=2,p_{3}=3}$ ${\displaystyle \lambda _{4}=(13)(1234)(13)=(1432)}$ ${\displaystyle \lambda_{5}}$ ${\displaystyle p_{1}=p_{2}=p_{3}=p_{4}=1}$ ${\displaystyle \lambda _{5}=(15)}$

上記の例から、における の剰余類の始まりを次のように選択することで、同様の方法でより高次の へ誘導的に進むことができます。偶数の場合、剰余類の始まりがすべて 1 に等しくなるように選択し、奇数の場合、剰余類の始まりが に等しくなるように選択します。このような選択により、「最後の」順列は奇数 の場合に、偶数の場合に( ) になります。これらの明示的な式を使用することで、最小限の計算で、特定のインデックスの順列をカウント/生成ステップで簡単に計算できます。このために、インデックスを階乗基数で表すと便利です。たとえば、インデックスの順列はとなり、最終的に となります。 ${\displaystyle k}$ ${\displaystyle S_{k}}$ ${\displaystyle S_{k+1}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle (1,2,\dots ,k)}$ ${\displaystyle \lambda _{k}=(1k)}$ ${\displaystyle k}$ ${\displaystyle \lambda_{k}=(1k_{-})(12\cdots k)(1k_{-})}$ ${\displaystyle k}$ ${\displaystyle k_{-}=k-1}$ ${\displaystyle 699=5(5!)+4(4!)+1(2!)+1(1!)}$ ${\displaystyle \sigma =\lambda _{2}(13)\lambda _{2}(15)\lambda _{4}(15)\lambda _{4}(15)\lambda _{4}(15)\lambda _{4}(56)\lambda _{5}(46)\lambda _{5}(36)\lambda _{5}(26)\lambda _{5}(16)\lambda _{5}=}$ ${\displaystyle \lambda_{2}(13)\lambda_{2}((15)\lambda_{4})^{4}(\lambda_{5})^{-1}\lambda_{6}=(23)(14325)^{-1}(15)(15)(123456)(15)=}$ ${\表示スタイル (23)(15234)(123456)(15)}$ ${\displaystyle \sigma =(1653)(24)}$

スワップ順列による乗算は計算時間が短く、生成される新しい順列ごとにスワップ乗算を1回だけ行うため、この生成手順は非常に効率的です。さらに、単純な式が存在するため、各順列の最後の順列を取得することで、 予想よりも少ないステップで特定のインデックスを持つ順列に直接移動でき、さらに時間を節約できます。これは、スワップごとに処理するのではなく、サブグループのブロックごとに処理できるためです。 ${\displaystyle S_{k}}$

アプリケーション

順列は、ターボ符号などの誤り検出・訂正アルゴリズムのインターリーバー要素 で用いられます。例えば、3GPP Long Term Evolutionモバイル通信規格では、この考え方が用いられています（3GPP技術仕様36.212 ^[65] を参照）。このような応用では、特定の望ましい特性を満たす順列を高速に生成する方法が求められます。その方法の一つは、順列多項式に基づいています。また、ユニーク順列ハッシュにおける最適ハッシュの基盤としても用いられています。^[66]

参照

• 数学ポータル

• 交互順列
• 畳み込み
• 循環順序
• 偶数と奇数の順列
• ヨセフスの順列
• レヴィ＝チヴィタのシンボル
• 順列トピックのリスト
• 主要指数
• 順列カテゴリ
• 順列群
• 順列パターン
• 順列表現（対称群）
• 確率
• ランコント番号
• ソーティングネットワーク
• 換字暗号
• スーパーパターン
• 超順列
• 十二倍の道
• 順列の弱い順序

注記

1. 1は非可換群の単位元を表すためによく使われる。
2. 順序は暗黙的に理解されることが多い。整数の集合は小さいものから大きいものの順に自然に表記され、文字の集合は辞書式順序で表記される。その他の集合については、自然な順序を明示的に指定する必要がある。
3. より正確には、繰り返しのない変化形。この用語は他の言語でも依然として一般的であり、現代英語では翻訳で最も頻繁に登場する。
4. この例における自然な順序は、元の単語の文字の順序です。
5. 古い文献では、circular permutation がcyclic permutationの同義語として使われることがありましたが、現在ではそうではありません。Carmichael (1956, p. 7) を参照。

参考文献

1. ウェブスター（1969）
2. マッコイ（1968年、152ページ）
3. ネリング（1970年、86ページ）
4. ヒース、トーマス・リトル (1981). 『ギリシャ数学史』ニューヨーク: ドーバー出版. ISBN 0-486-24073-8. OCLC  7703465。
5. Broemeling, Lyle D. (2011年11月1日). 「アラブ暗号学における初期の統計的推論の解説」. The American Statistician . 65 (4): 255– 257. doi :10.1198/tas.2011.10191. S2CID  123537702.
6. Biggs, NL (1979). 「組合せ論の根源」. Historia Math . 6 (2): 109– 136. doi :10.1016/0315-0860(79)90074-0.
7. ステッドマン 1677、4ページ。
8. ステッドマン 1677、5ページ。
9. ステッドマン 1677、6～7頁。
10. ステッドマン 1677、8ページ。
11. ステッドマン 1677、13–18ページ。
12. Rejewski, Marian (1980). 「エニグマ暗号解読における順列理論の応用」. Applicationes Mathematicae . 16 (4): 543– 559. doi : 10.4064/am-16-4-543-559 . ISSN  1233-7234.
13. Cash, David (2019). 「CMSC 28400 暗号化入門 2019年秋 - ノート#2: 順列とエニグマ」(PDF) .
14. Scheinerman, Edward A. (2012年3月5日). 「第5章 関数」.数学：離散数学入門（第3版）. Cengage Learning. 188ページ. ISBN 978-0840049421. 2020年2月5日時点のオリジナルよりアーカイブ。2020年2月5日閲覧。順列を表すには、小文字のギリシャ文字（特にπ、σ、τ）を使用するのが慣例である。
15. ロットマン 2002、41ページ
16. ボガート 1990, 487ページ
17. キャメロン 1994、29ページ、脚注3。
18. Conway, John H.; Burgiel, Heidi; Goodman-Strauss, Chaim (2008). The Symmetries of Things . AK Peters. p. 179.順列――例えば、複数の人の名前の順列――は、名前または人のいずれかを移動させるものと考えることができます。別名の観点では、順列は各人に新しい名前または別名を割り当てるものと見なされます（ラテン語のalias = 別の場所に由来）。一方、アリバイの観点では、人々を新しい名前に対応する場所に移動します（ラテン語のalibi = 別の場所に由来）。
19. 「順列表記法 - Wikiversity」. en.wikiversity.org . 2024年8月4日閲覧。
20. アラバマ州コーシー (1815 年 1 月)。 「Mémoire Sur le Nombre des Valeurs qu'une Fonction peut acquérir, lorsqu'on y permute de toutes les manières possibles les quantités qu'elle renferme」[関数内で、関数に含まれる変数をあらゆる可能な方法で並べ替えたときに、関数が取得できる値の数についての回想録]。Journal de l'École Polytechnique (フランス語)。10：1～ 28。 4ページをご覧ください。
    • 英語翻訳
21. Wussing, Hans (2007), 『抽象群概念の起源：抽象群理論の起源史への貢献』 Courier Dover Publications, p. 94, ISBN 9780486458687コーシーは、1815 年に、配列を上下に書き、両方を括弧で囲む順列記法を初めて使用しました。
22. ボガート 1990, 17ページ
23. ガースタイン 1987, 217ページ
24. Aigner, Martin (2007). 『列挙のコース』 Springer GTM 238. pp. 24–25. ISBN 978-3-540-39035-0。
25. ホール 1959、54ページ
26. Bona 2012, p.87 [この本には誤植/誤りがあり、(54)ではなく(45)が示されています。]
27. スタンレー、リチャード・P. (2012).列挙的組合せ論：第1巻、第2版. ケンブリッジ大学出版局. p. 30, Prop 1.3.1. ISBN 978-1-107-01542-5。
28. キタエフ、セルゲイ（2011年）『順列と単語のパターン』シュプリンガー・サイエンス＆ビジネス・メディア、119頁。ISBN 978-3-642-17333-2。
29. ビッグス、ノーマン・L.; ホワイト、AT (1979).順列群と組み合わせ構造. ケンブリッジ大学出版局. ISBN  978-0-521-22287-7。
30. ディクソン, ジョン・D.; モーティマー, ブライアン (1996).順列群. シュプリンガー. ISBN  978-0-387-94599-6。
31. キャメロン、ピーター・J. (1999).順列群. ケンブリッジ大学出版局. ISBN  978-0-521-65302-2。
32. Jerrum, M. (1986). 「順列群のコンパクト表現」. J. Algorithms . 7 (1): 60– 78. doi :10.1016/0196-6774(86)90038-6. S2CID  18896625.
33. 「組み合わせと順列」www.mathsisfun.com . 2020年9月10日閲覧。
34. Weisstein, Eric W. 「順列」. mathworld.wolfram.com . 2020年9月10日閲覧。
35. ウスペンスキー 1937年、18ページ
36. チャラランビデス, Ch A. (2002). 列挙的組合せ論. CRC Press. p. 42. ISBN 978-1-58488-290-9。
37. ブルアルディ 2010、p. 46、定理2.4.2
38. ブルアルディ 2010、47ページ
39. ブルアルディ 2010、39ページ
40. ボナ 2012年、97～103頁。
41. セーガン、ブルース（2001）、対称群（第2版）、シュプリンガー、p.3
42. ハンフリーズ 1996年、84ページ。
43. ホール 1959、60ページ
44. ボナ 2004、4ページ以降。
45. ボナ 2012年、4～5頁。
46. ボナ2012、25ページ。
47. ボナ2012、109～110頁。
48. Slocum, Jerry; Weisstein, Eric W. (1999). 「15 – パズル」. MathWorld . Wolfram Research, Inc. 2014年10月4日閲覧。
49. ボナ2004、43ページ。
50. Bóna 2004、43ページ以降。
51. クヌース 1973年、12ページ。
52. HA Rothe、Sammlung combinatorisch-analytischer Abhandlungen 2 (ライプツィヒ、1800)、263–305。 Knuth 1973、p. で引用。 14
53. フィッシャー, RA; イェーツ, F. (1948) [1938].生物学、農業、医学研究のための統計表（第3版）. ロンドン: オリバー＆ボイド. pp.  26– 27. OCLC  14222135.
54. Bacher, A.; Bodini, O.; Hwang, HK; Tsai, TH (2017). 「コイン投げによるランダム順列の生成：古典アルゴリズム、新分析、そして現代実装」（ACM Trans. Algorithms 13(2): 24:1–24:43 ed.）pp.  24– 43.
55. Sedgewick, R (1977). 「順列生成法」(PDF) . Computing Surveys . 9 (2): 137– 164. doi :10.1145/356689.356692. S2CID 12139332. 2008年2月21日時点のオリジナルより アーカイブ(PDF) .
56. Knuth 2005、1–26ページ。
57. "std::next_permutation". cppreference.com . 2017年12月4日. 2018年3月31日閲覧。
58. Heap, BR (1963). 「Permutations by Interchanges」.コンピュータジャーナル. 6 (3): 293– 298. doi : 10.1093/comjnl/6.3.293 .
59. Mütze, Torsten; Sawada, Joe; Williams, Aaron. 「Generate permutations」. Combinatorial Object Server . 2019年5月29日閲覧。
60. Zaks, S. (1984). 「順列生成のための新しいアルゴリズム」. BIT Numerical Mathematics . 24 (2): 196– 204. doi :10.1007/BF01937486. S2CID  30234652.
61. Sawada, Joe; Williams, Aaron (2018). 「シグマ-タウ問題に対するハミルトン経路」.第29回ACM-SIAM離散アルゴリズムシンポジウム論文集, SODA 2018.ニューオーリンズ, ルイジアナ州: Society for Industrial and Applied Mathematics (SIAM). pp.  568– 575. doi : 10.1137/1.9781611975031.37 .
62. Corbett, PF (1992). 「ローテータグラフ：ポイントツーポイントマルチプロセッサネットワークのための効率的なトポロジ」. IEEE Transactions on Parallel and Distributed Systems . 3 (5): 622– 626. doi :10.1109/71.159045.
63. 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。
64. Popp, OT (2002).大きな順列を素早く処理する. priv. comm.
65. 「3GPP TS 36.212」。
66. Dolev, Shlomi; Lahiani, Limor; Haviv, Yinnon (2013). 「ユニーク順列ハッシュ」.理論計算機科学. 475 : 59–65 . doi : 10.1016/j.tcs.2012.12.047 .

参考文献

• ボガート、ケネス・P.（1990）、序論的組合せ論（第2版）、ハーコート・ブレース・ジョバノビッチ、ISBN 978-0-15-541576-8
• Bóna、Miklós (2004)、順列の組み合わせ、Chapman Hall-CRC、ISBN 978-1-58488-434-7
• Bona、Miklos (2012)、Combinatorics of Permutations (第 2 版)、CRC Press、ISBN 978-1-4398-5051-0
• Brualdi, Richard A. (2010) 『Introductory Combinatorics (第5版)』 Prentice-Hall, ISBN 978-0-13-602040-0
• キャメロン、ピーター・J.（1994）、組合せ論：トピック、テクニック、アルゴリズム、ケンブリッジ大学出版局、ISBN 978-0-521-45761-3
• カーマイケル、ロバート・D.（1956）[1937]、有限順序群論入門、ドーバー、ISBN 978-0-486-60300-1
• フレイリー、ジョン・B.（1976年）、抽象代数学入門（第2版）、Addison-Wesley、ISBN 0-201-01984-1
• ガースタイン、ラリー・J.（1987）、離散数学と代数構造、WHフリーマンアンドカンパニー、ISBN 978-0-7167-1804-8
• ホール、マーシャル・ジュニア（1959年）『群論』マクミラン
• ハンフリーズ、JF（1996）、群論講座、オックスフォード大学出版局、ISBN 978-0-19-853459-4
• クヌース、ドナルド（1973）「ソートと検索」、『コンピュータプログラミングの芸術』第3巻 この本では、演習 5.1.1–7 (p. 19) で、反転表の変種C ₁、...、C _nとして、Lehmer コード (その名前は使用していません)が他の 2 つの変種とともに言及されています。
• クヌース、ドナルド（2005年）、すべてのタプルと順列の生成、コンピュータプログラミングの芸術、第4巻、アディソン・ウェズレー、ISBN 978-0-201-85393-3第2巻、初版。
• マッコイ、ニール H. (1968)、『現代代数学入門、改訂版』、ボストン：アリン＆ベーコン、LCCN  68015225
• Nering, Evar D. (1970),線形代数と行列理論（第2版）、ニューヨーク：Wiley、LCCN  76091646
• ロットマン、ジョセフ・J.（2002）、Advanced Modern Algebra、Prentice-Hall、ISBN 978-0-13-087868-7
• ステッドマン、ファビアン（1677）、カンパナロジア、ロンドン 出版者は「WS」と記されており、これはウィリアム・スミスが「献辞」の宛名となっている 大学青年協会の代理人を務めていた可能性もある。引用符内の原文の長い「S」は、現代の短い「s」に置き換えられている。
• ウスペンスキー、ジェームズ（1937年）、数学的確率入門、マグロウヒル
• ウェブスター第7版大学用新辞典、スプリングフィールド：G. & C. メリアム社、1969年

さらに読む

• ビッグス、ノーマン L. (2002)、離散数学（第2版）、オックスフォード大学出版局、ISBN 978-0-19-850717-8
• フォアタ、ドミニク。 Schutzenberger、Marcel-Paul (1970)、Théorie Géométrique des Polynômes Eulériens、Lecture Notes in Mathematics、vol. 138、ベルリン、ハイデルベルク: Springer-Verlag、ISBN 978-3-540-04927-2リンクは、Springer-Verlag 社によって最初に出版されたテキストの、無料で入手可能な再入力（LaTeX 化）および改訂版へのリンクです。
• クヌース、ドナルド（1998年）、ソートと検索、コンピュータプログラミングの芸術、第3巻（第2版）、アディソン・ウェズレー、ISBN 978-0-201-89685-5セクション5.1:順列の組合せ論的性質、pp.11–72。
• セジウィック, ロバート (1977). 「順列生成法」. ACMコンピューティングサーベイ. 9 (2): 137– 164. doi : 10.1145/356689.356692 . S2CID  12139332.
• 小林正人 (2011). 「Bruhat順序の順列の下のビグラスマン順列の列挙」.秩序. 1 : 131–137 .

外部リンク

• 「順列」、数学百科事典、EMSプレス、2001 [1994]