Таблица 3

ОБРАЩЕНИЕ ПЕРЕСТАНОВКИ 621543 С ПОМОЩЬЮ АЛГОРИТМА I

Читать столбцы слева направо. В момент * цикл (16 3) уже был обращен.

Алгоритм I {Обратная перестановка на месте). Заменить Х[1]Л[2].. .Х[п], которая является перестановкой чисел {1,2,...,п}, обратной перестановкой. Этот алгоритм был предложен Бин-Чао Хуаном (Bing-Chao Huang) [Inf. Proc. Letters 12 (1981), 237-238].

11. [Инициализация.] Присвоить m n, j <--1.

12. [Следующий элемент.] Присвоить г +- Х[т]. Если г < О, перейти к шагу 15 (этот элемент уже был обработан).

13. [Обратить один элемент.] (В этот момент j < О и г = Х[т]. Если т не является наибольшим элементом своего цикла, то первоначальная перестановка давала X[-j] = т.) Присвоить Х[т] 4- j, j •<--m, m г, г <- Х[т].

14. [Конец цикла?] Если г > О, перейти к шагу 13 (этот цикл не закончен); иначе - присвоить г 4- j. (В последнем случае первоначальная перестановка давала А[-j] = m, где т -наибольший элемент в его цикле.)

15. [Сохранить окончательное значение.] Присвоить Х[гп] А--г. (Первоначально

Л[-г] было равно т.)

16. [Цикл по т.] Уменьшить m на 1. Если m > О, перейти к 12; в противном случае работа алгоритма заканчивается.

Пример данного алгоритма приведен в табл. 3. Этот метод основан на обращении последовательных циклов перестановки; для пометки обращенных элементов их делают отрицательными, а впоследствии восстанавливают первоначальный знак.

Алгоритм I частично напоминает алгоритм А и очень сильно напоминает алгоритм нахождения циклов, реализованный в программе В (строки 54-68). Таким образом, это типичный представитель алгоритмов, имеющих отношение к перестановкам. Во время подготовки его реализации для MIX было обнаружено, что удобнее всего сохранять в регистре величину -г, а не саму г.

Программа I {Обращение на месте). гИ = т; г12 = -г; г13 = j и п = N (этот символ определяется, когда программа транслируется как часть большей программы).

01 INVERT ENTl N 1 П. Инициализация, т i-п.

02 ENT3 -1 1 J -1.

Время выполнения этой программы легко подсчитать способом, о котором говорилось выше. Каждому элементу Х[т] сначала присваивается отрицательное значение на шаге 13, а затем - положительное на шаге 15. Общее время выполнения составляет (14iV--C-l-2)u, где N - размерность массива, а С - общее число циклов. Ниже будет проанализировано поведение С в случайной перестановке.

Почти всегда существует несколько алгоритмов решения любой поставленной задачи, поэтому можно ожидать, что есть еще один способ обращения перестановки. Следующий остроумный алгоритм был предложен Дж. Бутройдом (J. Boothroyd).

Алгоритм J {Обращение на месте). Этот алгоритм дает такой же результат, как и алгоритм I, но на основании другого метода.

Л. [Сделать все величины отрицательными.] Присвоить Х{к] i--Х[к] для 1 < < п.

Присвоить также т <г- п.

J2. [Инициализация j] Присвоить j 4- т.

J3. [Нахождение отрицательного элемента.] Присвоить г <- ХЦ]. Если г > О, присвоить j -h- i и повторить этот шаг.

J4. [Обращение.] Присвоить X[j] <- А[-г], Х[-г] 4- т.

J5. [Цикл по т.] Уменьшить т на 1; если m > О, вернуться к шагу J2. В противном случае работа алгоритма заканчивается.

Пример выполнения алгоритма Бутройда приведен в табл. 4. В сущности, в основе метода опять лежит циклическая структура, но в данном случае то, что алгоритм действительно решает поставленную задачу, гораздо менее очевидно. Мы предоставляем читателю проверить это самостоятельно (см. упр. 13).

Программа J {Аналог программы I). гИ = т; г12 = j; rI3 = -г.

01 INVERT ENNI N 1 Л. Сделать все величины отрицательными.

02 ST1 X+N+1,1(0:0) N Установить отрицательный знак.

03 INC1 1 N

04 J1N *-2 N Еще?

05 ENT1 N 1 m4-n.

06 2Н ENN3 0,1 N J2. Инициализация г i 4- т.

07 ENN2 0,3 А j i.

08 LD3N Х,2 А J3. Нахождение отрицательного элемента.

Таблица 4

обращение перестановки 62 1543 с помощью алгоритма j

09 10 11 12 13 Ц

DECl

*-2 X,3 X,2 X,3 1

A i > 0?

Л J4. Обращение.

N X[j]X[-i].

N X[-i] m.

N J5. Цикл no m.

N Переход к шагу J2, если m > О

Чтобы выяснить, насколько быстро работает данная программа, нужно знать величину А; она настолько интересна и поучительна, что мы оставили ее для упражнения (см. упр. 14).

Хотя алгоритм J невероятно изящен, анализ показывает, что алгоритм I намного его превосходит. На самом деле оказывается, что среднее время выполнения алгоритма J, в сущности, пропорционально nlnn, а среднее время выполнения алгоритма I пропорционально п. Возможно, кто-нибудь когда-нибудь найдет применение алгоритму J (или некоторой его модификации); это слишком изящный алгоритм, чтобы его можно было совсем забыть.

Замечательное соответствие. Как уже отмечалось, запись перестановки в циклическом виде не единственна; состоящую из шести элементов перестановку (1 6 3)(4 5) можно записать как (5 4)(3 1 6) и т. д. Поэтому полезно рассмотреть каноническую форму циклического представления, которая является единственной. Для получения канонической формы выполните следующие действия.

a) Выпишите явно все единичные циклы.

b) Внутри каждого цикла поместите на первое место наименьшее число.

c) Расположите циклы в порядке убывания их первых элементов.

Например, для перестановки (3 1 6)(5 4) получим

(а): (3 1 6) (5 4) (2); (Ь): (1 6 3) (4 5) (2); (с): (4 5) (2) (1 6 3). (20)

Важным свойством этой канонической формы является то, что скобки можно удалить, а затем восстановить единственным образом. Следовательно, расставить скобки в "4 5 2 1 6 3" для получения канонической циклической формы можно только единственным способом. Необходимо вставить левую скобку непосредственно перед каждым минимумом слева направо (т. е. перед тем элементом, перед которым нет меньшего элемента).