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

Пусть <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) = n + 1 - c(\pi)</math>, так что безопасным обращением будет являться такое, которое увеличивает <math>c(\pi)</math> и не создает неориентированных компонентов (это увеличило бы <math>t(\pi)</math>).

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

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

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

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

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