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

''Обращение'' <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> – последовательность обращений. Она сортирует перестановку ж, если ж ■ p\ ■ ■ ■ k = Id, где Id = (1; : : : ; n) – тождественная перестановка. Длина кратчайшей последовательности обращений при сортировке ж называется расстоянием обращения я и обозначается как d(jr).