Обратные перестановки. Алгоритмы
Каждая перестановка имеет себе обратную. Например, имеем перестановку
,
для нее обратной будет перестановка
.
Алгоритм I. (Обратная перестановка на месте). Заменим перестановку X[1], X[2] … X[n], которая является перестановкой чисел {1, 2, …, n}, обратной перестановкой.
I1. [Инициализация]. Присвоить m n, j -1.
I2. [Следующий элемент]. Присвоить i X[m]. Если i < 0, перейти к шагу I5 (этот элемент уже был обработан).
I3. [Обратить один элемент]. (В этот момент j < 0 и i = X[m]. Если m не является наибольшим элементом своего цикла, то первоначальная перестановка давала X[-j] = m). Присвоить X[m] j, j -m, m i, i X[m].
I4. [Конец цикла?]. Если i > 0, перейти к шагу I3 (этот цикл не закончен); иначе — присвоить i j. (В последнем случае первоначальная перестановка давала X[-j] = m, где m — наибольший элемент в его цикле.)
I5. [Сохранить окончательное значение]. Присвоить X[m] -i. (Первоначально X[-i] было равно m).
I6. [Цикл по m]. Уменьшить m на 1. Если m > 0, перейти к I2, в противном случае работа алгоритма заканчивается.
Пример. Найти обратную перестановку для строки: 6 2 1 5 4 3.
Решение.
В качестве второй строки запишем
порядковые номера цифр строки, получим:
Переставим строки
местами, получим:
.
Переставим столбцы местами, сохраняя
порядок элементов заданной строки,
получим
.
Таким образом, перестановка (3 2 6 4 5 1)
является результатом обращения исходной
строки 6 2 1 5 4 3.
Алгоритм J. (Обращение на месте). Этот алгоритм дает такой же результат, как и алгоритм I, но на основании другого подхода.
J1. [Сделать все величины отрицательными]. Присвоить X[k] -X[k] для 1 k n. Присвоить также m n.
J2. [Инициализация j]. Присвоить j m.
J3. [Нахождение отрицательного элемента]. Присвоить i X[j]. Если i > 0, то присвоить j i и повторить этот шаг.
J4. [Обращение]. Присвоить X[j] X[-i], X[-i] m.
J5. [Цикл по m]. Уменьшить m на 1, если m > 0, вернуться к шагу J2. В противном случае работа алгоритма заканчивается.
Хотя алгоритм J невероятно изящен, анализ показал, что алгоритм I намного его превосходит. На самом деле оказывается, что среднее время выполнения алгоритма J, в сущности, пропорционально n ln(n), а среднее время выполнения алгоритма I пропорционально n.
Запись перестановки в циклическом виде не единственна; состоящую из шести элементов перестановку (1 6 3) (4 5) (2) можно записать как (4 5) (3 1 6) (2) и другими способами, что вносит некоторую неопределенность. Поэтому важно рассмотреть каноническую форму циклического представления, которая является единственной.
Для получения канонической формы перестановки выполним следующие действия:
Вписать в перестановку пропущенные единичные циклы.
Внутри каждого цикла поместить на первое место наименьшее число.
Расположить циклы в порядке убывания их первых элементов.
Пример. Для циклической перестановки (3 1 6) (5 4) найти каноническое
представление.
Решение. (3 1 6) (5 4) (2) (1 6 3) (4 5) (2) (4 5) (2) (1 6 3).
Важным свойством канонической формы является то, что скобки можно опустить, а затем восстановить единственным образом.
Последовательность действий следующая:
1. Выбираем направление просмотра строки слева направо.
2. Расставляем “(“ в начале строки и “)” в конце строки.
3. Ищем минимальное число и, если перед ним еще не стоит “(“ ставим “(“
4. Перед “(“ ставим “)”.
5. Переходим к анализу нерассмотренных еще элементов строки.
6. Если еще не все элементы рассмотрены, переход к п. 3.
7. Конец алгоритма.
Пример. Написать каноническую форму для перестановки (6 4 3) (5 1 2)
Решение.
1. (6 4 3) (5 1 2)
2. (3 6 4) (1 2 5)
3. 3 6 4 1 2 5.
Обратный процесс введения скобок циклов будет следующим (3 6 4) (1 2 5).