Самая длинная чередующаяся подпоследовательность - Longest alternating subsequence

В комбинаторный математика, вероятность, и Информатика, в самая длинная чередующаяся подпоследовательность задача, кто-то хочет найти подпоследовательность заданного последовательность в котором элементы расположены в чередующемся порядке и в котором последовательность является максимально длинной.

Формально, если ${\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{and}}\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{and}}\qquad 1\leq i_{1}<i_{2}<\cdots <i_{k}\leq n.}$

Позволять ${\displaystyle {\rm {as}}_{n}(\mathbf {x} )}$ обозначают длину (количество членов) самой длинной чередующейся подпоследовательности ${\displaystyle \mathbf {x} }$. Например, если мы рассмотрим некоторые из перестановок целых чисел 1,2,3,4,5, мы получим, что

• ${\displaystyle {\rm {as}}_{5}(1,2,3,4,5)=2}$; потому что любая последовательность из 2 различных цифр (по определению) чередуется. (например 1,2 или 1,4 или 3,5)
• ${\displaystyle {\rm {as}}_{5}(1,5,3,2,4)=4,}$ потому что 1,5,3,4 и 1,5,2,4 и 1,3,2,4 все чередуются, и нет чередующейся подпоследовательности с большим количеством элементов;
• ${\displaystyle {\rm {as}}_{5}(5,3,4,1,2)=5,}$ потому что 5,3,4,1,2 сам по себе чередуется.

Эффективные алгоритмы

Задача самой длинной чередующейся подпоследовательности разрешима во времени ${\displaystyle O(n)}$, куда ${\displaystyle n}$ - длина исходной последовательности.^{[нужна цитата ]}

Результаты распространения

Если ${\displaystyle \mathbf {x} }$ случайная перестановка целых чисел ${\displaystyle 1,2,\ldots ,n}$ и ${\displaystyle A_{n}\equiv {\rm {as}}_{n}(\mathbf {x} )}$, то можно показать^[2][3][4]который

${\displaystyle E[A_{n}]={\frac {2n}{3}}+{\frac {1}{6}}\qquad {\text{and}}\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)}$.^[5]

В качестве ${\displaystyle n\rightarrow \infty }$оптимальное количество чередующихся выборок в режиме онлайн, правильно центрированных и масштабированных, сходится к нормальному распределению.^[6]

Смотрите также

• Альтернативная перестановка
• Шаблон перестановки и избегание шаблонов
• Подсчет локальных максимумов и / или локальных минимумов в заданной последовательности
• Критерии поворота для проверки статистической независимости ${\displaystyle n}$ наблюдения
• Количество чередующихся прогонов
• Самая длинная возрастающая подпоследовательность
• Самая длинная общая проблема подпоследовательности

Рекомендации

1. Стэнли, Ричард П. (2011), Перечислительная комбинаторика, Том I, второе издание, Издательство Кембриджского университета
2. Уидом, Гарольд (2006), «О предельном распределении длины самой длинной чередующейся последовательности в случайной перестановке», Электрон. J. Combin., 13: Исследования 25, 7
3. Стэнли, Ричард П. (2008), «Самые длинные чередующиеся подпоследовательности перестановок», Michigan Math. Дж., 57: 675–687, arXiv:математика / 0511419, Дои:10.1307 / mmj / 1220879431
4. Удре, Кристиан; Рестрепо, Рикардо (2010), «Вероятностный подход к асимптотике длины самой длинной знакопеременной подпоследовательности», Электрон. J. Combin., 17: Исследовательская статья 168, 19
5. Арлотто, Алессандро; Чен, Роберт В .; Шепп, Лоуренс А.; Стил, Дж. Майкл (2011), «Онлайн-выбор чередующихся подпоследовательностей из случайной выборки», J. Appl. Вероятно., 48 (4): 1114–1132, arXiv:1105.1558, Дои:10.1239 / jap / 1324046022
6. Арлотто, Алессандро; Стил, Дж. Майкл (2014), «Оптимальный онлайн-выбор чередующейся подпоследовательности: центральная предельная теорема», Adv. Appl. Вероятно., 46 (2): 536–559, Дои:10.1239 / aap / 1401369706