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

Ключевые слова и синонимы

Сортировка при помощи инверсий

Постановка задачи

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

Обращение [math]\displaystyle{ \rho = \rho_{i, j} (1 \le i \le j \le n) }[/math] представляет собой операцию, которая меняет порядок на противоположный и переключает знаки при элементах [math]\displaystyle{ \pi_i, ..., \pi_j }[/math] в перестановке [math]\displaystyle{ \pi }[/math]:

[math]\displaystyle{ \pi \cdot \rho = (\pi_1, ..., \pi_{i - 1}, - \pi_j, ..., - \pi_i, \pi_{j + 1}, ..., \pi_n) }[/math].

Пусть [math]\displaystyle{ \rho_1, ..., \rho_k }[/math] – последовательность обращений. Она сортирует перестановку [math]\displaystyle{ \pi }[/math], если [math]\displaystyle{ \pi \cdot \rho_1 \cdot \cdot \cdot \rho_k = Id }[/math], где Id = (1, ..., n) – тождественная перестановка. Длина кратчайшей последовательности обращений при сортировке [math]\displaystyle{ \pi }[/math] называется расстоянием обращения [math]\displaystyle{ \pi }[/math] и обозначается как [math]\displaystyle{ d(\pi) }[/math].

Если вычисление [math]\displaystyle{ d(\pi) }[/math] производится за линейное время [2] (см. статью «Расстояние обращений»), то вычисление последовательности размера [math]\displaystyle{ d(\pi) }[/math], выполняющей сортировку [math]\displaystyle{ \pi }[/math], является более сложным, и для него пока не разработано линейных алгоритмов. Наилучшие параметры сложности на данный момент демонстрирует решение Танье и Сагот [17], которое было теоретически улучшено в работах Танье, Бержерон и Сагот [18] и Хана [8].