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

'''Линейные или циклические перестановки'''

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

Пусть дана перестановка со знаками ж на множестве f1; 2 ng n элементов. Ее можно преобразовать в перестановку без знаков f{n) = Ti' = [n[,Ti!1,...,Ti!ln\ на множестве {1,2,...,2и} 2 и элементов путем замены каждого положительного элемента i двумя элементами 2i – 1, 2i (именно в таком порядке), а каждого отрицательного элемента -i – двумя элементами 2i, 2i - 1. Расширенная перестановка /(ж) здесь рассматривается как циклическая перестановка при помощи определения 2 n + 1 и 1 в индексах и элементах. Чтобы гарантировать, что каждая операция на /(ж) может быть имитирована операцией на ж, для f{ji) допускаются только операции, выполняющие разрезание перед нечетными позициями. Граф разрывов G(n) представляет собой граф с раскрашенными ребрами с 2n вершинами f1;2;:::; 2ng, в котором для любого 1 < i: < n вершина ji'2i соединяется с ж'21+1 ребром черного цвета, а вершина 2i присоединяется с 2i + 1 ребром серого цвета (см. пример на рис. 1b). Поскольку степень каждой вершины в G(JI) в точности равна 2, G(JI) уникальным образом разбивается на циклы. k-cycle (то есть цикл длины k) представляет собой цикл с k черными ребрами и является нечетным, если k нечетно. Обозначим количество нечетных циклов в G(JI) за со^(ж). Несложно убедиться в том, что G(TI) состоит из n 1-циклов и, следовательно, со^(ж) = n, если ж является тождественной перестановкой [1; 2... n ]. Гу и др. [ ] показали, что сосу(/х • ж) < сосу(тг) + 2 для всех линейных перестановок ж и операций ji. В работе [ ] Хартман и Шаран также отметили, что вышеприведенный результат имеет мест отакже для циклических перестановок, и доказали, что нижняя граница d(jr) составляет (и(лг) - соМ(ж))/2.