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

Перестановка со знаками ж = [ж\,%i, ..., ж„] из п{л) = и элементов представляет собой перестановку, в которой каждому элементу присвоен знак – плюс или минус. Сегментом я является последовательность последовательных элементов ж,-, лг,+ь ..., k , где 1 < i < k < n. Обращение р представляет собой операцию, которая меняет порядок элементов в сегменте на противоположный и при этом переключает их знаки. Два сегмента itj, Jij+\,..., ж^ и itj, Jij+\,...,Ж\ называются смежными, если j = k + 1 или i = l + 1. Транспозиция x представляет собой операцию, переставляющую друг с другом два смежных (непересекающихся) сегмента. Транспозиция-обращение (transreversal) xp^,B (XPB,A, соответственно) представляет собой транспозицию, которая переставляет два сегмента A и B и при этом выполняет обращение A (соответственно, B). Операция двойного обращения (revrev) pp выполняет обращение каждого из двух смежных сегментов (без перестановки их друг с другом). Задача нахождения кратчайшей последовательности операций транспозиции, транспозиции-обращения и двойного обращения, преобразующей заданную перестановку в тождественную, называется задачей сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений. Длина кратчайшей сортирующей последовательности обращений называется расстоянием обращения я и обозначается как d(jr).