Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5): различия между версиями

''Перестановка со знаками'' <math>\pi = [ \pi_1, \pi_2, ..., \pi_n]</math> на <math>n (\pi) = n</math> элементах представляет собой перестановку, в которой каждому элементу присвоен знак – плюс или минус. ''Сегментом'' <math>\pi</math> является последовательность последовательных элементов <math>\pi_i, \pi_{i + 1}, ..., \pi_k</math>, где <math>1 \le i \le k \le n</math>. ''Обращение'' <math>\rho</math> представляет собой операцию, которая меняет порядок элементов в сегменте на противоположный и при этом переключает их знаки. Два сегмента <math>\pi_i, \pi_{i + 1}, ..., \pi_k</math> и <math>\pi_j, \pi_{j + 1}, ..., \pi_l</math>, называются ''смежными'', если j = k + 1 или i = l + 1. ''Транспозиция'' <math>\tau</math> представляет собой операцию, переставляющую друг с другом два смежных (непересекающихся) сегмента. ''Транспозиция-обращение'' (transreversal) <math>\tau \rho_{A, B}</math> (<math>\tau \rho_{B, A}</math>, соответственно) представляет собой транспозицию, которая переставляет два сегмента A и B и при этом выполняет обращение A (соответственно, B). Операция ''двойного обращения'' (revrev) <math>\rho \rho</math> выполняет обращение каждого из двух смежных сегментов (без перестановки их друг с другом). Задача нахождения кратчайшей последовательности операций транспозиции, транспозиции-обращения и двойного обращения, преобразующей заданную перестановку в тождественную, называется задачей сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений. Длина кратчайшей сортирующей последовательности обращений называется расстоянием обращения <math>\pi</math> и обозначается как <math>d(\pi)</math>.

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

Операция действует как на затронутые сегменты, так и на элементы этих сегментов. Две операции ji и fi' эквивалентны, если они имеют один и тот же результат перегруппировки, т.е. fi-ж = fi' -ж для всех ж. В работе [8] Хартман и Шаран показали, что для элемента x циклической перестановки ж и операции ji, действующей на x, существует эквивалентная операция ji', не действующая на x. Основываясь на этом свойстве, они доказали, что задача сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений эквивалентна линейным и циклическим перестановкам. Кроме того, они заметили, что операции транспозиций-обращений и двойных обращений являются эквивалентными для циклических перестановок (как показано на рис. 1a), из чего следует, что задача сортировки линейной или циклической перестановки при помощи транспозиций, транспозиций-обращений и двойных обращений может быть сведена к задаче сортировки циклической перестановки при помощи транспозиций и транспозиций-обращений.