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

''Подписанная перестановка'' <math>\pi</math> размера n представляет собой перестановку над множеством {-n, ... , -1, 1, ..., n}, где <math>\pi_{- 1} = - \pi_i</math> для всех i.

''Обращение'' <math>\rho = \rho_{i, j} (1 \le i \le j \le n)</math> представляет собой операцию, которая меняет порядок на противоположный и меняет знаки при элементах <math>\pi_i, ..., \pi_j</math> в перестановке <math>\pi \cdot \rho = (\pi_1, ..., \pi_{i - 1}, - \pi_j, ..., - \pi_i, \pi_{j + 1}, ..., \pi_n)</math>.

Пусть <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>d(\pi)</math>.