Д. Кнут - Искусство программирования том 1 (1119450), страница 47
Текст из файла (страница 47)
Обратные перестановки. Обратная перестановка я для перестановки;г — это такая перестановка, которая отменяет действие щ если в я элемент 1 переходит в 5 я, то в я элемент 5 переходит в Е Таким образом, произведение яя равняется тождественной перестановке; то же самое справедливо и для произведения я .г. Обратную перестановку часто обозначают через я ', а не я, но верхний индекс 1 явно лишний [по той же причине, по которой х~ = х).
Каждая перестановка имеет обратную. Например, обратной перестановкой для аЬсбеу соуЬеа аЬсбеу Рассмотрим некоторые простые алгоритмы вычисления обратной перестановки. Предположим, что в оставшейся части раздела мы будем иметь дело с перестановками чисел (1,2,..., и).
Если Х[Ц Х[2]... Х[п] — такая перестановка, то существует простой метод вычисления перестановки, обратной к ней. Присвоим У[Х[к]] ~-?с для 1 < lс < п. Тогда У[1] 1'[2]... У[п] — искомая обратная перестановка. В этом методе используется 2п ячеек памяти, а именно — п для Х и п для У. А теперь ради интереса предположим, что и очень велико, в то время как нужно вычислить обратную перестановку к Х[1] Х[2]... Х[п], не используя слишком много дополнительного пространства памяти.
Необходимо вычислить обратную перестановку "на месте", чтобы после окончания работы алгоритма массив Х [1] Х [2]... Х [и] представлял собой перестановку, обратную к первоначальной. Простое присвоение Х[Х[?с]] < — А для 1 <?с < п в этом случае, разумеется, не пройдет, но, рассматривая циклическую структуру, можно получить следующий простой алгоритм. Таблица 3 ОБРАЩЕНИЕ ПЕРЕСТАНОВКИ 621543 С ПОМОЩЬЮ АЛГОРИТМА 1 13 13 6 — 3 2 2 -6 -б 5 5 4 4 — 1 -1 1 б — 3 — 1 б — 1 15 15 -3 3 2 2 б б 5 5 4 4 1 1 2 1 — 2 — 2 — 2 -3 15* 12 -3 — 3 2 2 — 6 -б 5 5 4 4 1 1 б 5 — 1 — 1 — 1 4 После шага 12 13 6 6 2 2 1 1 5 5 4 4 3 — 1 б 3 -1 — 6 3 1 12 15 -3 — 3 2 2 -б -б -5 5 4 4 1 1 4 4 — 4 — 4 — 5 — 5 15 13 -3 — 3 2 — 4 б б 5 5 4 4 1 1 3 2 — 4 — 2 — 6 — 4 13 -3 2 -6 5 — 1 1 — 5 5 13 15 — 3 — 3 2 2 †-б — 5 — 5 -1 4 1 1 5 5 — 4 — 4 — 1 -4 Х(1] Х(2] Х[3] Х [4] Л [5] Х[6] Читать столбцы слева направо.
В момент ь цянл (163) ужв был обращен. Программа 1 (Обращение на месте). г11 = т; г12 ь— з — 1; г13 ж 1' и н = й (этот символ определяется, когда программа транслируется как часть большей программы). ° РИГЕЬТ ЬИН В 1 ~~. И ог Ейтз -1 1 2 4- -1. Алгоритм 1 (Обратнал перестановка на месте).
Заменить Х(1]Х[2]...Х[п], которая является перестановкой чисел (1,2,...,н), обратной перестановкой. Этот алгоритм был предложен Вин-Чао Хуаном (В1пб-СЬао Нпапб) [1пб Ргос. Т,ессегв 12 (1981), 237 — 238]. 11. [Инициализация.] Присвоить т +- н, 1' 4- — 1. 12. [Следующий элемент.] Присвоить 1 4 — Л[т]. Если 1 < О, перейти к шагу 15 (этот элемент уже был обработан). 13.
[Обратить один элемент.] (В этот момент 1 < О и 1 = Х[т]. Если 1п не является наибольшим элементом своего цикла, то первоначальная перестановка давала Х[ — 1] = т.) Присвоить Л (т] +- 1, 1 4 — -т, т +- г, 1 4 — Х[т!. 14. [Конец цикла?) Если 1 > О, перейти к шагу 13 (этот цикл не закончен); иначе— присвоить 1 +- 11 (В последнем случае первоначальная перестановка давала Х(-А = т, где т — наибольший элемент в его цикле.) 15. [Сохранить окончательное значение.] Присвоить Л [т] +- -1.
(Первоначально Х( — 4] было равно т.) 16. [Цикл по т.] Уменьшить т на 1. Если т > О, перейти к 12; в противном случае работа алгоритма заканчивается. 1 Пример данного алгоритма приведен в табл. 3. Этот метод основан на обращении последовательных циклов перестановки; для пометки обращенных элементов их делают отрицательными, а впоследствии восстанавливают первоначальный знак. Алгоритм 1 частично напоминает алгоритм А и очень сильно напоминает алгоритм нахождения циклов, реализованный в программе В (строки 54-68). Таким образом, это типичный представитель алгоритмов, имеющих отношение к перестановкам.
Во время подготовки его реализации для И1Х было обнаружено, что удобнее всего сохранять в регистре величину — 1, а не саму 4. Время выполнения этой программы легко подсчитать способом, о котором говорилось выше. Каждому элементу Л[т] сначала присваивается отрицательное значение на шаге 13, а затем — положительное на шаге 15. Общее время выполнения составляет (14]Н+С+2)и, где ]Н вЂ” размерность массива, а С вЂ” общее число циклов. Ниже будет проанализировано поведение С в случайной перестановке. Почти всегда существует несколько алгоритмов решения любой поставленной задачи, поэтому можно ожидать, что есть еще один способ обращения перестановки.
Следующий остроумный алгоритм был предложен Дж. Бутройдом (3. ВоогЬгоу4). Алгоритм 3 (Обращение но месте). Этот алгоритм дает такой же результат, как и алгоритм 1, но на основании другого метода. 31. [Сделать все величины отрицательными.] Присвоить Х[к] с — — Х[к] для 1 < к < и. Присвоить также т +- и. 32. [Инициализация 3.] Присвоить 1 ~- т. 33. [Нахождение отрицательного элемента.] Присвоить г' е- Х[3]. Если 1 > О, присвоить 3' +- 1 и повторить этот шаг. 34.
[Обращение.] Присвоить Х[А <- Х[ — 1], Х[ — э] +- т. 35. [Цикл по т.] Уменьшить т на 1; если тп > О, вернуться к шагу 32. В противном случае работа алгоритма заканчивается. ! Пример выполнения алгоритма Бутройда приведен в табл. 4. В сущности, в основе метода опять лежит циклическая структура, но в данном случае то, что алгоритм действительно решает поставленную задачу, гораздо менее очевидно. Мы предоставляем читателю проверить это самостоятельно (см. упр. 13). Программа 3 (Аналог программа 1), гП = гп; г12 = 3'; г13 — = — 1. 01 1ИНЕНТ ЕМИ1 М 1 03 Зт1 Х+И+1,1(0:О) ?Н 03 1ИС1 1 ?Н 04 31М *-2 ?Н О5 ЕИТ1 М 1 Об 2Н ЕММЗ 0,1 ?Н 07 ЕМИ2 0,3 А ОВ ЫЗИ Х,2 А Л. С елать асс величины от иг агельными. Установить отрицательный знак. Еще? т+- и.
э. ич 1 +- $. 33 Нахо ение от и агельного элемента. 03 2Н 04 05 ЗН Об 07 ов 00 4Н 10 11 5Н 13 6Н 53 Ы2И Х,1 32Р 5Г ' зтз Х,1 ЕМИЗ 0,1 ЕИИ1 0,2 102И Х,1 32И ЗВ ЕИМ2 0,3 ЗТ2 Х,1 ОЕС1 1 31Р 2В Х 12. Сле ю ий элемент. 1+- Х[т]. 1Н Переход к шагу 15, если 1 < О. ?Н 13. Об ахать элемент. Л[т]+-3'. ?Н 1 +- — т. ?Н т+-1.
Ж 5+- Х[т]. Ч К~. ?П «и, ~ О. С В противном случае присвоить 1+- 31 Х 15. Сох внять окончательное значение Л[т]+- -1, э у~~ Ж Переход к шагу 12, если т > О. 1 Таблица 4 ОБРАЩЕНИЕ ПЕРЕСТАНОВКИ 621543 С ПОМОЩЬЮ АЛГОРИТМА .1 После шага ЛЗИ 4-2 ЬОА Х,З ЗТА Х,2 ЯТ1 Х„З РЕС1 1 Л1Р 2В А 1>02 ж 406 1'ч' Х[1] 4 — Х[ — 1]. А Х[-;]- .
Ю Дб Ярщ.цч.а 1у Переход к шагу Л2, если т > О 1 Чтобы выяснить, насколько быстро работает данная программа, нужно знать величину А; она настолько интересна и поучительна, что мы оставили ее для упражнения (см. упр. 14). Хотя алгоритм Л невероятно изящен, анализ показывает, что алгоритм 1 намного его превосходит. На самом деле оказывается, что среднее время выполнения алгоритма Л, в сущности, пропорционально п 1п н, а среднее время выполнения алгоритма 1 пропорционально п. Возможно, кто-нибудь когда-нибудь найдет применение алгоритму Л (или некоторой его модификации); это слишком изящный алгоритм, чтобы его можно было совсем забыть.
Замечательное соответствие. Как уже отмечалось, запись перестановки в циклическом виде не единственна; состоящую из шести элементов перестановку (1 6 3)(4 5) можно записать как (5 4)(3 1 б) и т. д. Поэтому полезно рассмотреть каноническую форму циклического представления, которая является единственной. Для получения канонической формы выполните следующие действия. а) Выпишите явно все единичные циклы. Ь) Внутри каждого цикла поместите на первое место наименьшее число.
с) Расположите циклы в порядке убивания их первых элементов. Например, для перестановки (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" для получения канонической циклической формы можно только единственным способом. Необходимо вставить левую скобку непосредственно перед каждым минимумом слева направо (т.
е. перед тем элементом, перед которым нет меньшего элемента). 09 10 11 12 10 14 Л[Ц Х[2] Х[3] Л [4] Х[5] Х[6] Л2 ЛЗ Л5 -б — 6 †— 2 — 2 — 2 — 1 — 1 6 — 5 — 5 -5 -4 — 4 — 4 — 3 — 3 — 1 б б 5 — 3 — 3 б 6 б ЛЗ 35 ЛЗ Л5 — 6 -б †— 6 -2 -2 -2 — 2 б б б б -5 5 5 5 -4 -5 — 5 4 — 1 -1 -1 — 1 5 4 4 3 — 4 — 4 -5 -5 5 5 5 5 ЛЗ Л5 ЛЗ вЂ” 6 3 3 — 2 — 2 — 2 б б 6 5 5 5 4 4 4 — 1 †-б 3 2 2 -1 — 1 -2 б б 2 Л5 ЛЗ Л5 3 3 3 2 2 2 6 6 6 5 5 5 4 4 4 -б — б 1 1 1 О -2 — б — б 2 6 6 Это свойство канонической формы позволяет получить замечательное однозначное соответствие между' множеством всех перестановок, представленных в циклическом виде, н множеством всех перестановок, представленных в линейной форме.
Например, канонической формой для перестановки б 2 1 5 4 3 является (4 5) (2) (1 б 3); удалив скобки, получим перестановку 4 5 2 1 б 3, циклической формой которой является (2 5 б 3) (1 4); удалив скобки, получим 2 5 б 3 1 4, циклической формой которой является (3 б 4) (1 2 5) и т. д. Это соответствие имеет многочисленные применения в изучении перестановок различных типов. Например, зададимся вопросом: "Сколько циклов имеет перестановка из п элементов в среднем?".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
