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

Вторая часть представляет собой «узкое место» всей процедуры. На этот момент неориентированных компонентов уже не осталось, расстояние составляет <math>d(\pi) = n + 1 - c(\pi)</math>, так что безопасным обращением будет являться такое, которое увеличивает <math>c(\pi)</math> и не создает неориентированных компонентов (это увеличило бы <math>t(\pi)</math>).

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