предыдущее состояние) только строкой а;; и новое значение в строке х - это значение, которое исчезло в результате предыдущего изменения. Короче говоря, имеем следующий алгоритм.

Алгоритм В {Перемножение перестановок, представленных в виде циклов). Этот алгоритм (рис. 21) дает, в сущности, тот же результат, что и алгоритм А. Предположим, что переставляемыми элементами являются Х\,Х2, ,Хп- Будем использовать вспомогательную таблицу Г[1],Т[2],...,Г[п]; по окончании работы алгоритма Xi переходит в Xj в перестановке ввода тогда и только тогда, когда T[i] = j.

Bl. [Инициализация.] Присвоить 1[к] к, где \ <к <п. Подготовиться также к просмотру справа налево.

82. [Следующий элемент.] Рассмотреть следующий элемент ввода (справа налево). Если ввод исчерпан, то работа алгоритма заканчивгьется. Если рассматривгьется элемент ")", то присвоить Z О и повторить шаг В2; если это элемент "(", то перейти к шагу В4. В противном случгье рассматривается элемент Xi для некоторого i; тогда перейти к шагу ВЗ.

83. [Замена T[i].] Выполнить взаимный обмен Z Т\г\. Если в результате получится T[i] = О, то присвоить j i. Вернуться к шагу В2.

84. [Замена Г[;].] Присвоить T[j] Z. (Здесь j-это строка, определяющая элемент ")" в обозначениях табл. 2, т. е. правую скобку, которая соответствует только что просмотренной левой скобке.) Вернуться к шагу В2.

Инициализация

.1 /")"

ХЗледующий элемент/йТ»

Готово

Рис. 21. Алгоритм В: перемножение перестановок.

Разумеется, после выполнения этого алгоритма необходимо еще вывести содержимое таблицы Т в циклическом виде; как будет показано ниже, это легко сделать методом "пометок".

Теперь на основе нового алгоритма давайте напишем программу для MIX. Будем придерживаться тех же основных правил, что и в программе А, используя такой же формат ввода и вывода, как и раньше. Но тут возникает небольшая проблема: как можно реализовать алгоритм В, не зная наперед, чему равны элементы xi,X2,... ,х„? Неизвестно, чему равно п, а также будет ли элемент Ь равен Xi или Х2 и т. д. Существует простой способ решения данной проблемы - создать таблицу, внести в нее имена элементов, которые уже встречались, и каждый раз искать имя текущего элемента (см. строки 35-44 в программе ниже).

Программа В (Дает тот же результат, что и программа А). гХ = Z; г14 = г; гП = j; rI3 = п, количество различных просмотренных имен.

01 MAXWDS EQU

02 X ORIG

03 Т ORIG

04 PERM ORIG

05 ANS EQU

06 OUTBUF ORIG

07 CARDS EQU

1200

♦+MAXWDS ♦+MAXWDS ♦+MAXWDS PERM *+24 16

МаксимЕшьная длина ввода. Таблица имен.

Вспомогательная таблица состояния. Входная перестановка. Место для ответа. Место для печати.

Совпадают со строками 05-22 программы А. В этот момент г12 слов

ввода находятся в PERM, PERM + 1, ... и мы пока еще не видели ни одного имени. Присвоить Z 0.

82. Следующий элемент.

Пропустить пробелы. Следующим элементом является ")"? Это "("?

Приготовиться к поиску. Сохранить в начале таблицы. Искать в таблице имен.

Повторять до нахождения соответствия. Это имя появлялось ранее? Нет; увеличить размер таблицы. Вставить новое имя Хп-Присвоить Т[п] «- п, i <г- п.

83. Замена Г[г]. Сохранить Z. Установить Z.

Если Z было нулем, присвоить j +- г.

84. Зг.менг.Т\1].

Вернуться к В2, если работа еще не закончена.

Весь ввод просмотрен. Таблицы х кТ содержат ответ. Теперь построим циклическую запись. Имя было помечено? Это единичный цикл?

Открыть цикл.

Пометить имя.

Г Найти элемент, в который переходит этот элемент. Т

Т Он уже помечен?

W Да, цикл закрывается.

Z Перейти к следующему имени.

Совпадают со строками 48-62 программы А.

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

Опыт показывает, что основная часть времени выполнения программы В будет потрачена на поиск в таблице имен; это время определяется параметром F. Существуют более эффективные алгоритмы поиска и построения словарей имен; они называются алгоритмами таблиц символов и играют важную роль в прикладной математике. В главе 6 мы займемся всесторонним исследованием эффективных алгоритмов таблиц символов.

Обратные перестановки. Обратная перестановка тг" для перестановки тг - это такая перестановка, которая отменяет действие тг; если в тг элемент г переходит в j IT, то в 7г~ элемент j переходит в г. Таким образом, произведение тгтг" равняется тождественной перестановке; то же самое справедливо и для произведения 7г~7г. Обратную перестановку часто обозначают через п", а не тг", но верхний индекс 1 явно лишний (по той же причине, по которой = х).

Каждая перестановка имеет обратную. Например, обратной перестановкой для

а Ь с d е f\ fс d f b е

, , , является , ,

cdfbea) \а b с d е

а\ f а b с d е f\ f) ~ \f d а b е с)

Рассмотрим некоторые простые алгоритмы вычисления обратной перестановки.

Предположим, что в оставшейся части раздела мы будем иметь дело с перестановками чисел {1,2, ...,п}. Если А[1] Х[2]... [п] - такая перестановка, то существует простой метод вычисления перестановки, обратной к ней. Присвоим У[А[А;]] 4- к для I <к <п. Тогда У[1] У[2]... У[п] - искомая обратная перестановка. В этом методе используется 2п ячеек памяти, а именно - п для Х и п для Y.

А теперь ради интереса предположим, что п очень велико, в то время как нужно вычислить обратную перестановку к [l] АГ[2]... АГ[п], не используя слишком много дополнительного пространства памяти. Необходимо вычислить обратную перестановку "на месте", чтобы после окончания работы алгоритма массив [l] Х[2]... Х[п] представлял собой перестановку, обратную к первоначальной. Простое присвоение [ArfA;]] 4- к для 1 <к <пъ этом случае, разумеется, не пройдет, но, рассматривая циклическую структуру, можно получить следующий простой алгоритм.