最長交代部分列

組合せ数学、確率論、およびコンピュータサイエンスにおいて、最長交代部分列問題では、与えられた数列の要素が交代順で並び、かつ可能な限り長い部分列を見つけることが目的とされます。

正式には、${\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}$は異なる実数の列であり、その部分列は${\displaystyle \{x_{i_{1}},x_{i_{2}},\ldots ,x_{i_{k}}\}}$交互に^{[ 1 ]}（またはジグザグまたは上下）である場合

${\displaystyle x_{i_{1}}>x_{i_{2}}<x_{i_{3}}>\cdots x_{i_{k}}\qquad {\text{かつ}}\qquad 1\leq i_{1}<i_{2}<\cdots <i_{k}\leq n.}$

同様に、${\displaystyle \mathbf {x} }$逆交互（または上下）の場合

${\displaystyle x_{i_{1}}<x_{i_{2}}>x_{i_{3}}<\cdots x_{i_{k}}\qquad {\text{かつ}}\qquad 1\leq i_{1}<i_{2}<\cdots <i_{k}\leq n.}$

長さ1のシーケンスはすべて、交互配列かつ逆交互配列であることに注意してください。

させて${\displaystyle {\rm {as}}_{n}(\mathbf {x} )}$は、最長交代部分列の長さ（項数）を表す。${\displaystyle \mathbf {x} }$例えば、整数 1,2,3,4,5 の順列のいくつかを考えると、次のようになります。

• ${\displaystyle {\rm {as}}_{5}(5,4,3,2,1)=2}$長さ2の交互部分列（例えば5,4、5,2、3,1）は存在するが、長さ3のすべての部分列が交互ではないためである。
• ${\displaystyle {\rm {as}}_{5}(1,2,3,4,5)=1}$なぜなら、長さ2のすべての部分列は交代列ではないからである（実際には、それらは逆交代列である）。
• ${\displaystyle {\rm {as}}_{5}(5,1,3,4,2)=4,}$5,1,3,2、5,1,4,2、5,3,4,2はすべて交互の列であり、それ以上の要素を持つ交互の部分列は存在しないからです。
• ${\displaystyle {\rm {as}}_{5}(4,3,5,1,2)=5,}$なぜなら、4、3、5、1、2はそれ自体が交互の数字だからである。

異なる要素の列において、局所極値（隣接する両方の要素よりも大きい要素、または隣接する両方の要素よりも小さい要素）の部分列は、標準的な最長交代列を形成する。^{[ 2 ]}その結果、列の最長交代部分列は、${\displaystyle n}$要素は時間の中に見出すことができる${\displaystyle O(n)}$繰り返しが可能なシーケンスでは、まず繰り返し要素の各連続をその要素の単一のコピーに置き換えた後、同じ方法を適用できます。

もし${\displaystyle \mathbf {x} }$整数のランダムな順列${\displaystyle 1,2,\ldots ,n}$そして${\displaystyle A_{n}\equiv {\rm {as}}_{n}(\mathbf {x} )}$^{すると、 [ 3 ] [ 4 ] [ 5 ]} が示すことができる。

${\displaystyle E[A_{n}]={\frac {2n}{3}}+{\frac {1}{6}}\qquad {\text{および}}\qquad \operatorname {Var} [A_{n}]={\frac {8n}{45}}-{\frac {13}{180}}.}$

さらに、${\displaystyle n\rightarrow \infty }$確率変数${\displaystyle A_{n}}$適切に中心化およびスケーリングすると、標準正規分布に収束します。

最長交代部分列問題はオンラインアルゴリズムの設定でも研究されており、その要素は${\displaystyle \mathbf {x} }$それらはオンライン形式で提示され、意思決定者は、将来提示される要素について何も知らず、また過去の観察結果を思い出すこともできない状態で、各要素が最初に提示された時点で、それらを含めるか除外するかを決定する必要がある。

数列が与えられた場合${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$共通の連続分布を持つ独立な確率変数${\displaystyle F}$交互選択の期待値を最大化する選択手順を構築することが可能です。このような期待値は厳密に推定でき、それは${\displaystyle (2-{\sqrt {2}})n+O(1)}$[ ^{6 ]​}

として${\displaystyle n\rightarrow \infty }$適切な中心化とスケーリングを行った最適なオンライン交互選択の数は正規分布に収束する。^{[ 7 ]}

• 交互順列
• 順列パターンとパターン回避
• 与えられた数列における局所最大値および／または局所最小値を数える
• 統計的独立性をテストするための転換点テスト${\displaystyle n}$観察結果
• 交互実行回数
• 最長増加部分列
• 最長共通部分列