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

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

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

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

Вспомним, что существует линейный алгоритм для вычисления расстояния обращений по формуле d{n) = n + 1 — с{ж) + фг) (нотация из работы [ ]), где с(ж) – количество циклов в графе разрывов, а фг) вычисляется из неориентированных компонентов перестановки (см. статью «Расстояние обращений»). После расчета этого показателя тривиальный алгоритм вычисляет последовательность размера d(jr): на очередном шаге алгоритма пробовать каждое возможное обращение p, до тех пор, пока не будет найдено такое, что d(ж ■ p) = сфг) - 1. Такое обращение называется безопасным. Этот подход требует O(n) вычислений для каждого возможного обращения (они занимают не более (n + 1)(n + 2)/2 = O(n2)); в результате итераций для поиска последовательности получаем алгоритм со сложностью O(n4).

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

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

Вторая часть представляет собой «узкое место» всей процедуры. На этот момент неориентированных компонентов уже не осталось, расстояние составляет d(jr) = n + 1 — с(ж), так что безопасным обращением будет являться такое, которое увеличивает с(ж) и не создает неориентированных компонентов (это увеличило бы фг)).

Обращение, увеличивающее фг), называется ориентированным. Найти ориентированное обращение несложно: его определяют любые два последовательных числа в перестановке, имеющих разные знаки. Гораздо сложнее убедиться в том, что это действие не увеличивает число неориентированных компонентов.

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

Алгоритм основан на следующей теореме, приведенной в работе [ ]. Последовательность ориентированных обращений Pi,.: ; , k называется максимальной, если не существует ориентированного обращения в ж • pi • • • k. В частности, последовательность сортировки является максимальной, в то же время обратное неверно.

Теорема 1. Если последовательность S является максимальной, но не является последовательностью сортировки ориентированных обращений для перестановки, то существует непустая последовательность S0 ориентированных обращений, такая, что S может быть разбита на две части S = S1; S2, и S1; S0; S2 является последовательностью ориентированных обращений.

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

Этот алгоритм, с классической структурой данных для представления перестановок (например, в виде массива), также имеет сложность O(n2), поскольку на каждом этапе он должен провести проверку на наличие ориентированного обращения и применить его к перестановке.

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

Недавно Хан [8] предложил еще одну структуру данных, позволяющую выбирать и применять ориентированное обращение за время O(pn); аналогичная небольшая модификация, вероятно, поможет снизить сложность алгоритма в целом до O(n3/2).

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