Сортировка перестановок со знаками при помощи обращений (последовательность обращений)

Ключевые слова и синонимы

Сортировка при помощи инверсий

Постановка задачи

Подписанная перестановка [math]\displaystyle{ \pi }[/math] размера n представляет собой перестановку над множеством {-n, ... , -1, 1, ..., n}, где [math]\displaystyle{ \pi_{- i} = - \pi_i }[/math] для всех i.

Обращение [math]\displaystyle{ \rho = \rho_{i, j} (1 \le i \le j \le n) }[/math] представляет собой операцию, которая меняет порядок на противоположный и переключает знаки при элементах [math]\displaystyle{ \pi_i, ..., \pi_j }[/math] в перестановке [math]\displaystyle{ \pi }[/math]:

[math]\displaystyle{ \pi \cdot \rho = (\pi_1, ..., \pi_{i - 1}, - \pi_j, ..., - \pi_i, \pi_{j + 1}, ..., \pi_n) }[/math].

Пусть [math]\displaystyle{ \rho_1, ..., \rho_k }[/math] – последовательность обращений. Она сортирует перестановку [math]\displaystyle{ \pi }[/math], если [math]\displaystyle{ \pi \cdot \rho_1 \cdot \cdot \cdot \rho_k = Id }[/math], где Id = (1, ..., n) – тождественная перестановка. Длина кратчайшей последовательности обращений при сортировке [math]\displaystyle{ \pi }[/math] называется расстоянием обращения [math]\displaystyle{ \pi }[/math] и обозначается как [math]\displaystyle{ d(\pi) }[/math].

Если вычисление [math]\displaystyle{ d(\pi) }[/math] производится за линейное время [2] (см. статью «Расстояние обращений»), то вычисление последовательности размера [math]\displaystyle{ d(\pi) }[/math], выполняющей сортировку [math]\displaystyle{ \pi }[/math], является более сложным, и для него пока не разработано линейных алгоритмов. Наилучшие параметры сложности на данный момент демонстрирует решение Танье и Сагот [17], которое было теоретически улучшено в работах Танье, Бержерон и Сагот [18] и Хана [8].

Основные результаты

Вспомним, что существует линейный алгоритм для вычисления расстояния обращений по формуле [math]\displaystyle{ d(\pi) = n + 1 - c(\pi) + t(\pi) }[/math] (нотация из работы [4]), где [math]\displaystyle{ c(\pi) }[/math] – количество циклов в графе разрывов, а [math]\displaystyle{ t(\pi) }[/math] вычисляется из неориентированных компонентов перестановки, см. статью «Расстояние обращений»). После расчета этого показателя тривиальный алгоритм вычисляет последовательность размера [math]\displaystyle{ d(\pi) }[/math]: на очередном шаге алгоритма пробовать каждое возможное обращение p, до тех пор, пока не будет найдено такое, что [math]\displaystyle{ d(\pi \cdot \rho) = d(\pi) - 1 }[/math]. Такое обращение называется безопасным. Этот подход требует O(n) вычислений для каждого возможного обращения (они занимают не более [math]\displaystyle{ (n + 1)(n + 2)/2 = O(n^2)) }[/math]; в результате итераций для поиска последовательности получаем алгоритм со сложностью [math]\displaystyle{ O(n^4) }[/math].

Первый полиномиальный алгоритм Ханненхалли и Певзнера [9] не мог обеспечить лучшую сложность, и его история началась с алгоритмических исследований процесса поиска кратчайшей последовательности обращений.

Сценарий обращений

Все опубликованные решения для вычисления последовательности сортировок делятся на две части, следуя разбиению формулы расстояния на два параметра: первый тип решений вычисляет последовательность обращений таким образом, что полученная перестановка не имеет неориентированных компонентов; второй тип сортирует все ориентированные компоненты.

Лучшее решение для первой части предложили Каплан, Шамир и Тарьян [10]; их алгоритм выполняется за линейное время при сочетании с линейным алгоритмом вычисления расстояния [2], он основан на ранних находках Ханненхалли и Певзнера [9].

Вторая часть представляет собой «узкое место» всей процедуры. На этот момент неориентированных компонентов уже не осталось, расстояние составляет [math]\displaystyle{ d(\pi) = n + 1 - c(\pi) }[/math], так что безопасным обращением будет являться такое, которое увеличивает [math]\displaystyle{ c(\pi) }[/math] и не создает неориентированных компонентов (это увеличило бы [math]\displaystyle{ t(\pi) }[/math]).

Обращение, увеличивающее [math]\displaystyle{ t(\pi) }[/math], называется ориентированным. Найти ориентированное обращение несложно: его определяют любые два последовательных числа в перестановке, имеющих разные знаки. Гораздо сложнее убедиться в том, что это действие не увеличивает число неориентированных компонентов.

Квадратичные алгоритмы, разработанные, с одной стороны, Берманом и Ханненхалли [5], а с другой – Капланом, Шамиром и Тарьяном [10], основаны на распознавании безопасных обращений за линейное время. На данный момент не известно улучшенных алгоритмов распознавания безопасных обращений, и представляется, что нижняя граница уже была достигнута, о чем свидетельствуют Озери-Флато и Шамир в работе [14], в которой они сообщили, что «главный вопрос в исследованиях перестановок геномов заключается в том, можно ли получить субквадратичный алгоритм для сортировки при помощи обращений». Этот алгоритм был получен Танье и Сагот [17], которые доказали, что распознавание безопасного обращения на каждом этапе не является необходимым; требуется только распознавание ориентированные обращений.

Алгоритм основан на следующей теореме, приведенной в работе [18]. Последовательность ориентированных обращений [math]\displaystyle{ \rho_1, ..., \rho_k }[/math] называется максимальной, если не существует ориентированного обращения в [math]\displaystyle{ \pi \cdot \rho_1 \cdot \cdot \cdot \rho_k }[/math]. В частности, последовательность сортировки является максимальной, в то же время обратное неверно.

Теорема 1. Если последовательность S является максимальной, но не является последовательностью сортировки ориентированных обращений для перестановки, то существует непустая последовательность S' ориентированных обращений, такая, что S может быть разбита на две части [math]\displaystyle{ S = S_1, S_2 }[/math], и [math]\displaystyle{ S_1, S', S_2 }[/math] является последовательностью ориентированных обращений.

Это позволяет строить последовательность ориентированных обращений вместо безопасных обращений и увеличивать их размер за счет добавления обращений внутрь последовательности, а не в ее конец, получая последовательность сортировки.

Этот алгоритм, с классической структурой данных для представления перестановок (например, в виде массива), также имеет сложность [math]\displaystyle{ O(n^2) }[/math], поскольку на каждом этапе он должен провести проверку на наличие ориентированного обращения и применить его к перестановке.

Небольшая модификация структуры данных, предложенная Капланом и Вербином [11], позволяет выбирать и применять ориентированное обращение за время [math]\displaystyle{ O(\sqrt{n \; log \; n}) }[/math]; с ее помощью алгоритм Танье-Сагот достигает временной сложности [math]\displaystyle{ O(n^{3/2} \sqrt{log \; n}) }[/math].

Недавно Хан [8] предложил еще одну структуру данных, позволяющую выбирать и применять ориентированное обращение за время [math]\displaystyle{ O(\sqrt{n}) }[/math]; аналогичная небольшая модификация, вероятно, поможет снизить сложность алгоритма в целом до [math]\displaystyle{ O(n^{3/2}) }[/math].

Пространство оптимальных решений

Почти все исследования последовательностей сортировки для обращений были ориентированы на выдачу строго одной последовательности, хотя было замечено, что нередко этих последовательностей оказывается много (даже для [math]\displaystyle{ n \le 10 }[/math] их может быть несколько миллионов). Лишь несколько исследований попытались восполнить этот пробел.

Алгоритм перечисления всех безопасных обращений на одном этапе был предложен и реализован Сипелем [16]. Структуру пространства оптимальных решений открыли Шаве и др. [3]; алгоритмические подходы к этой структуре исследовались в работе [6].