Сортировка перестановок со знаками при помощи обращений (последовательность обращений): различия между версиями
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
''Подписанная перестановка'' <math>\pi</math> размера n представляет собой перестановку над множеством {-n, ... , -1, 1, ..., n}, где <math>\pi_{- | ''Подписанная перестановка'' <math>\pi</math> размера n представляет собой перестановку над множеством {-n, ... , -1, 1, ..., n}, где <math>\pi_{- i} = - \pi_i</math> для всех i. | ||
''Обращение'' <math>\rho = \rho_{i, j} (1 \le i \le j \le n)</math> представляет собой операцию, которая меняет порядок на противоположный и | ''Обращение'' <math>\rho = \rho_{i, j} (1 \le i \le j \le n)</math> представляет собой операцию, которая меняет порядок на противоположный и переключает знаки при элементах <math>\pi_i, ..., \pi_j</math> в перестановке <math>\pi</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>\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>\pi</math> и обозначается как <math>d(\pi)</math>. | |||
Версия от 15:00, 18 февраля 2019
Ключевые слова и синонимы
Сортировка при помощи инверсий
Постановка задачи
Подписанная перестановка [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].