что, опять же, означает "а переходит в с, с переходит в f, f переходит в а, b переходит в d, d переходит в 6". Цикл {xi Х2 Хп) означает "xi переходит в Х2, Хп-1 переходит- Хп, Хп переходит в a;i". Так как элемент е является в перестановке фиксированным (т. е. переходит не в какой-либо другой элемент, а в самого себя), он не появляется в циклической записи. Таким образом, единичные циклы типа "(е)" записывать не принято. Если в перестановке фиксированными являются все элементы, так что присутствуют только единичные циклы, то она называется тождественной перестановкой и обозначается "()".

Запись перестановки в виде цикла не является единственной. Например,

{bd){acf), icfa){bd), {db){fac) (3)

и т. д. эквивалентны (2). Но запись "(afc) (bd)" уже не будет им эквивалентна, так как она означает, что а переходит в /.

Легко видеть, почему перестановку всегда можно представить в виде цикла. Начиная с элемента xi, перестановка переводит, скажем, xi в Х2, хг в а;з и т. д., пока наконец (поскольку количество элементов ограничено) мы не придем к некоему элементу Xn+i, который уже встречался среди х\,...,Хп. Этот элемент Xn+i должен быть равен xi. Предположим, он равен хз. Но это невозможно, так как известно, что Х2 переходит в хз, а по предположению в Xn+i переходит Хп ф Х2- Поэтому а;„4.1 = х\ и получаем цикл {х\Х2... а;„), являющийся частью перестановки для некоторого п > 1. Если этим циклом вся перестановка не исчерпывается, то существует элемент j/i, такой, что у\ ф г, для всех г, для которого аналогичным образом получим еще один цикл (j/i уг • • Ут)- Ни один у, не может равняться любому Жг, так как из ж, = j/j следует, что a;,+i = j/j+i и т. д. В конце концов для некоторого к получим xk = J/i, что противоречит предположению о выборе у\. Действуя подобным образом, можно найти все циклы, содержащиеся в перестановке.

В программировании эти понятия применяются каждый раз, когда некоторый набор из п объектов нужно расположить в другом порядке. Чтобы переупорядочить объекты, не перемещая их в какое-либо другое место, необходимо, в сущности, придерживаться циклической структуры. Например, чтобы переупорядочить (1), т. е. присвоить

(а, 6, с, d. е, /) (с, d, /, 6, е, а),

будем следовать циклической структуре (2) и последовательно присваивать

t •(- а, а •(- с, с /. / t: t •(- 6, 6 •(- d, d*t.

Но нужно отдавать себе отчет в том, что любое подобное преобразование можно осуществлять в непересекающихся циклах.

Произведения перестановок. Две перестановки можно перемножить в том смысле, что их произведение означает применение одной перестановки вслед за другой. Например, если за перестановкой (1) следует перестановка

abode f\ b d с а f е

то получим, что а переходит в с, которое затем переходит в с; Ь переходит в d, которое затем переходит в а и т. д.:

fа Ь с d е f\ (abed \с d f b е а J \b d с а

e f f e

abode f\ fс d f b e a\ a) \c a e d f bJ

с d f b e a b с d e f\

с a e d f bJ-

Вполне очевидно, что произведение перестановок не обладает свойством коммутативности; другими словами, tti х тгг необязательно равно тгг х тгх, где тгх и 7г2-перестановки. Читатель может убедиться в том, что, если поменять местами сомножители, произведение в (4) даст другой результат (см. упр. 3).

Кое-кто перемножает перестановки справа налево, вместо того чтобы делать это более естественным образом слева направо, как показано в (4). Фактически математики разделились на два лагеря: одни считают, что результат последовательного применения преобразований Tj и Тз следует обозначать через Т1Т2, а другие - через Т2Т1. Здесь мы будем использовать обозначение Т1Г2.

Пользуясь циклической записью, запишем равенство (4) следующим образом:

{acf){bd){abd){ef) = {acefb). (5)

Обратите внимание на то, что знак умножения "х" принято опускать; это не противоречит циклической записи, так как легко видеть, что перестановка (асf){bd) на самом деле является произведением перестановок (acf) и (bd).

Произведение перестановок можно вьшолнять непосредственно с помощью циклической записи. Например, вычислив произведение перестановок

{acf9){bcd){aed){fade){bgfae), (6)

находим (двигаясь слева направо), что "а переходит в с, с переходит sd, d переходит в а, а переходит sdndостается без изменений". Таким образом, конечным результатом (6) является то, что а переходит в d, и мы запишем \ad в качестве частичного ответа. Теперь выясним, что происходит с d: d переходит в Ь, которое затем переходит в д"; следовательно, имеем частичный результат "{adg". Рассмотрев, что происходит с д, находим, что "д переходит в а, затем в е, в /ива"; таким образом, первый цикл замыкается: "(adg)". Теперь выберем новый элемент, который еще не встречался, например с. Находим, что с переходит в е, и читатель может проверить, что окончательным ответом для (6) будет "(adg)(се6)".

А теперь попробуем выполнить эту процедуру с помощью компьютера. Следующий алгоритм формализует описанный выше метод таким образом, чтобы его можно было выполнить с помощью компьютера.

Алгоритм А {Перемножение перестановок, представленных в виде циклов). Этот алгоритм (рис. 20) берет произведение циклов, такое как (6), и вычисляет получающуюся в результате перестановку в виде произведения непересекающихся циклов. Для простоты здесь не приводится описание процедуры удаления единичных циклов; это было бы лишь незначительным обобщением алгоритма. По мере выпол-

CURRENT \найден

Просмотр формулы

Достигнут конец

flaVcURRENT = START?

Рис. 20. Алгоритм А (перемножение перестановок).

нения алгоритма последовательно "помечаем" элементы исходной формулы, т. е. те символы, которые уже "обработаны".

А1. [Первый проход.] Отметить все левые скобки и заменить все правые скобки помеченной копией входного символа, который следует за соответствующей левой скобкой (см. пример в табл. 1).

А2. [Раскрытие скобок.] Выполнив поиск слева направо, найти первый непомеченный элемент входной формулы. (Если все элементы помечены, то работа алгоритма заканчивается.) Установить START равным этому элементу; вывести левую скобку; вывести элемент и пометить его.

A3. [Установка CURRENT.] Установить CURRENT равным следующему элементу формулы.

А4. [Просмотр формулы.] Продвигаться вправо, пока не будет либо достигнут конец формулы, либо найден элемент, равный CURRENT; в последне.м случае пометить его и вернуться к щагу A3.

А5. [CURRENT = START?] Если CURRENT ф START, вывести CURRENT и вернуться к шагу А4, снова начав с левого края формулы (продолжая тем самым вывод искомого цикла).

А6. [Закрытие.] (Полный искомый цикл выведен.) Вывести правую скобку и вернуться к шагу А2. I

Например, рассмотрим формулу (6). В табл. 1 показаны последовательные этапы ее обработки. В первой строке таблицы приведена формула после замены правых скобок начальными элементами соответствующих циклов. В последующих строках показан процесс обработки формулы по мере пометки все большего числа элементов. Курсор указывает на текущий элемент, подлежащий обработке. В результате будет выведено следующее выражение: {adg){ceb){fУ. Обратите внимание, что в выводе присутствует единичный цикл.

Программа для MIX. Чтобы реализовать этот алгоритм для MIX, "пометки" можно делать с помощью знака слова. Предположим, что входная формула перфорирована на картах в следующем формате: состоящая из 80 колонок карта разделена на 16 полей по 5 символов. Каждое поле представляет собой один из следующих вариантов: (а) "uuuuC, что обозначает левую скобку начала цикла; (Ь) ")uuuu",