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

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

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

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

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

Обращение [math]\displaystyle{ \rho = \rho_{i, j} (1 \le i \le j \le n) }[/math] представляет собой операцию, которая меняет порядок на противоположный и меняет знаки при элементах 7Г,■,... , j в перестановке ж: Ж = (jTl,..., JTj-1, —Jtj, . . . , —Jtj, Jtj+l, . . . ,Jtn).

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

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