スタックソート可能な順列

数学およびコンピュータサイエンスにおいて、スタックソート可能な順列（ツリー順列とも呼ばれる）^{[ 1 ]}は、内部ストレージが単一のスタックデータ構造に限定されているアルゴリズムによって要素をソートできる順列である。スタックソート可能な順列は、順列パターン231を含まない順列であり、カタラン数で数えられ、ディックパスや二分木など、同じ計数関数を持つ他の多くの組み合わせオブジェクトと一対一で配置することができる。

スタックを使用して入力シーケンスをソートする問題は、最初にクヌース（1968）によって提起され、彼は以下の線形時間アルゴリズムを提示しました（後の「すべての最も近いより小さい値」問題のアルゴリズムと密接に関連しています）。

• 空のスタックを初期化する
• 各入力値xについて：
  • スタックが空ではなく、xがスタックの最上位項目より大きい間、スタックから出力にポップする
  • xをスタックにプッシュする
• スタックが空でない間は、出力にポップする

クヌースは、このアルゴリズムが一部の入力シーケンスを正しくソートする一方で、他のシーケンスをソートできないことを指摘した。例えば、シーケンス 3,2,1 は正しくソートされる。3 つの要素はすべてスタックにプッシュされ、1,2,3 の順にポップされる。しかし、シーケンス 2,3,1 は正しくソートされない。アルゴリズムは最初に 2 をプッシュし、より大きな入力値 3 を見つけると 2 をポップするため、2 は 1 の後ではなく前に出力される。

このアルゴリズムは比較ソートであるため、その成否は入力シーケンスの数値には依存せず、それらの相対的な順序のみに依存します。つまり、入力は、同じ長さのソート済みシーケンスからその入力を生成するために必要な順列によって記述できます。クヌースは、このアルゴリズムが正しくソートする順列を、順列パターン231（入力にそれぞれの順序で現れる3つの要素x、 y、 z、z 、 z  < x < y）を含まない順列であると特徴づけました。さらに、アルゴリズムが入力のソートに失敗した場合、その入力は単一のスタックではソートできないことを彼は観察しました。   

クヌースの研究は、より複雑なスタックシステムや関連するデータ構造を用いたソートに関するその後の多くの研究に影響を与えただけでなく、^{[ 2 ]}順列パターンや禁止パターンによって定義される順列クラスの研究のきっかけとなった。

クヌースのソートアルゴリズムがスタックソート可能な順列をソートする際に実行するプッシュとポップのシーケンスは、ディック言語を形成します。プッシュを左括弧、ポップを右括弧と解釈し直すと、バランスの取れた括弧の文字列が生成されます。さらに、すべてのディック文字列はこのようにしてスタックソート可能な順列から生成され、2つの異なるスタックソート可能な順列はそれぞれ異なるディック文字列を生成します。このため、長さnのスタックソート可能な順列の数は、長さ 2 nのディック文字列の数（カタラン数）と同じです。

${\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}.}$^{[ 3 ]}

スタックソート可能な順列は、（ラベルなし）二分木（計数関数がカタラン数の列である別の組み合わせクラス）と直接変換することもできます。二分木は、ノードを左から右の順に番号付けし、次にこれらの番号を木の先行順走査で訪問される順序（最初にルート、次に左部分木、次に右部分木、各部分木内で再帰的に継続）でリストすることにより、スタックソート可能な順列に変換できます。逆方向には、スタックソート可能な順列は、順列の最初の値xが木のルートに対応し、次のx − 1 個の値が再帰的にデコードされてルートの左の子が得られ、残りの値が再び再帰的にデコードされて右の子が得られる木にデコードできます。^{[ 1 ]}  

スタックソート可能な順列と一対一対応となる他のいくつかのクラスの順列も存在します。例えば、パターン132、213、312を回避する順列は、それぞれスタックソート可能な（231回避）順列から、順列を反転させる、順列内の各値xをn  +  1 − xに置き換える、あるいはこれらの操作を組み合わせることによって生成できます。312回避順列は231回避順列の逆順列でもあり、スタック上で入力からプッシュし出力へポップする操作を連続して行うことで恒等順列から生成できる順列であるため、スタック実現可能順列と呼ばれています。^{[ 4 ]}クヌース (1968)が指摘した ように、123 回避順列と 321 回避順列も、スタックソート可能な順列とはあまり直接関係がないにもかかわらず、同じ計数機能を持っています。  

Rotem (1981) は、与えられた長さのすべての順列の中から一様にランダムに選択されたスタックソート可能な順列の特性を調査した。そのような順列における最長降順列の期待値は次の通りである。${\displaystyle {\sqrt {\pi n}}-O(1)}$制約のないランダム順列とは定数倍だけ異なり（その期待値は約$\displaystyle 2\sqrt n$) 最長昇順列の期待値は、制約のない順列とはさらに大きく異なり、 ${\displaystyle (n+1)/2}$順列内の値のうち、これまでのすべての値よりも大きい値の期待値はわずかです。${\displaystyle 3-6/(n+2)}$制約のない順列の場合の対数値よりも小さい。また、反転の期待値は$\displaystyle \Theta (n^{3/2})$とは対照的に、$\displaystyle \Theta (n^{2})$制約のない順列の場合。

すべての順列は順列グラフを定義します。順列グラフの頂点は順列の要素であり、辺は順列によって反転される要素のペアを結びます。スタックソート可能な順列の順列グラフは自明に完全です。^{[ 4 ]}

順列pの各要素iについて、b _{i を}iの左にあり、かつiより大きい他の要素の数と定義する。このとき、pがスタックソート可能であるのは、すべてのiについて、b _i − b _{i + 1} ≤ 1 である場合に限る。 ^{[ 1 ]}      

Knott (1977) は、スタックソート可能な順列と二分木の間の全単射を利用して、各二分木の数値ランクを定義し、木のランクを計算する（「ランキング」）および与えられたランクを持つ木を計算する（「アンランキング」）ための効率的なアルゴリズムを構築しました。

Micheli & Rossin (2006) は、順列に対する 2 つの編集操作、すなわち削除 (順列パターンの作成) とその逆を定義しました。木と順列の間の同じ対応関係を使用して、これらの操作が木の辺の縮約とその逆に対応することを観察しました。木における編集距離に対する多項式時間動的計画法アルゴリズムを適用することにより、2 つのスタックソート可能な順列間の編集距離 (したがって最長共通パターンも) が多項式時間で見つけられることを示しました。この手法は後に、分離可能な順列の最長共通パターンを見つけるアルゴリズムに一般化されました。^{[ 5 ]}ただし、最長共通パターン問題は任意の順列に対して NP 完全です。^{[ 6 ]}

• Avis, David ; Newborn, Monroe (1981)、「直列ポップスタックについて」、Utilitas Mathematica、19 : 129–140、MR 0624050 。
• Bóna, Miklós (2002)、「スタックソート分野の概観」、Electronic Journal of Combinatorics、9 (2) A1、doi : 10.37236/1693、MR 2028290 。
• Bouvel, Mathilde; Rossin, Dominique; Vialette, Stéphane (2007)、「順列間の最長共通分離可能パターン」、Combinatorial Pattern Matching (CPM 2007)、Lecture Notes in Computer Science、vol.  4580、Springer、pp. 316–327、doi : 10.1007/978-3-540-73437-6_32、ISBN  978-3-540-73436-9。
• Felsner, Stefan; Pergel, Martin (2008)、「スタックとキューのネットワークを用いたソートの複雑性」、Algorithms - ESA 2008、Lecture Notes in Computer Science、vol.  5193、カールスルーエ、ドイツ、pp. 417–429、doi : 10.1007/978-3-540-87744-8_35、ISBN  978-3-540-87743-1{{citation}}: CS1 maint: 場所の発行元が見つかりません (リンク)。
• Knott, Gary D. (1977年2月)、「二分木のための番号付けシステム」、Communications of the ACM、20 (2): 113–115、doi : 10.1145/359423.359434。
• クヌース、ドナルド（1968）「第1巻：基本アルゴリズム」、コンピュータプログラミングの技法、マサチューセッツ州レディング：アディソン・ウェスリー。
• ミケリ、アンヌ；ロッシン、ドミニク（2006）「ラベルなし順序付きツリー間の編集距離」、理論情報学と応用、40（4）：593–609、arXiv：math/0506538、doi：10.1051/ita:2006043、MR 2277052、S2CID 2259835  。
• Rosenstiehl, Pierre ; Tarjan, Robert E. (1984)、「ガウス符号、平面ハミルトングラフ、およびスタックソート可能な順列」、Journal of Algorithms、5 (3): 375–390、doi : 10.1016/0196-6774(84)90018-X、MR 0756164 
• Rotem, D. (1981)、「スタックソート可能な順列」、離散数学、33 (2): 185–196、doi : 10.1016/0012-365X(81)90165-5、MR 0599081 。
• Tarjan, Robert (1972年4月)、「キューとスタックのネットワークを用いたソート」、Journal of the ACM、19 (2): 341–346、doi : 10.1145/321694.321704。