Подстановки в системе GAP

Вернуться к списку примеров

Алгоритм умножения подстановок

Напомним, что взаимно однозначное отображение множества M первых n натуральных чисел на себя называется подстановкой n-й степени. Если x - элемент множества M, и s - подстановка, то образ элемента x под действием подстановки s обозначается s(x). Тогда умножение подстановок определяется как композиция отображений:

(s1*s2)(x) = s1(s2(x)).

Подстановки являются стандартными объектами в системе GAP. Они задаются в виде произведения независимых циклов. При этом умножение подстановок выполняется слева направо, а не справа налево. Это связано с тем, что для образа точки i под действием подстановки p можно использовать как обозначение p(i), так и обозначение i^p. В GAP принят за основу второй вариант записи (поскольку запись p(i) интерпретировалась бы как обращение к функции p с аргументом i), и i^p записывается как i^p. Тогда выполняется соотношение i^(p1*p2)=(i^p1)^p2, соответствующее правилу (p₁*p₂)(i) = p₁(p₂(i)).

Для изучения алгоритма умножения подстановок справа налево приведем пример программы на языке GAP. Эта программа работает с подстановками, заданными в виде произведения независимых циклов в формате [[a₁,a₂,...,a_i],[b₁,b₂,...,b_j],...,[z₁,z₂,...,z_k]]. Мы вводим свою запись подстановок, отличную от принятой в GAP, специально для изучения правила умножения подстановок, и ни в коем случае не для практического применения в научных целях, так как в системе GAP уже имеется намного более эффективная возможность работы с подстановками. Данная программа также дает понятие о языке программирования GAP, так как содержит примеры его основных конструкций: условные переходы и три различных вида циклов - for, while и until.

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

ProductOfTwoPermutations:=function( s1, s2 ) local c, i, p, points, pos, s, t, x; s := Concatenation( s1, s2 ); if ForAny(s, x -> Length( x ) <> Length( Set( x ) ) ) then Error("An argument do not represent a permutation !!!"); fi;
t := []; points := Set( Flat( s ) ); while Length(points) > 0 do c := []; p := Minimum( points ); Add( c, p ); repeat for i in [ Length(s), Length(s)-1 .. 1 ] do if p in s[i] then pos := Position( s[i], p ); if pos = Length( s[i] ) then p := s[i][1]; else p := s[i][pos+1]; fi; fi; od; if p <> c[1] then Add( c, p ); fi; until p = c[1]; Add( t, c ); SubtractSet( points, c ); od; return Filtered( t, x -> Length( x ) > 1 ); end;Введя данную функцию, мы можем воспользоваться ей следующим образом:

gap> ProductOfTwoPermutations([[2,3,5,4],[1,6]], [[1,3,5]]); [ [ 1, 5, 6 ], [ 2, 3, 4 ] ]
Теперь более детально прокомментируем каждую строку программы:

ProductOfTwoPermutations:=function( s1, s2 ) # Используемые переменные: local t, # результирующий список независимых циклов s, # объединенный список независимых циклов из разложений # подстановок s1 и s2 (сначала перечисляются циклы из # разложения подстановки s1, потом подстановки s2) points, # множество точек, которые входят в запись s1 и s2 p, # текущая точка i, # счетчик циклов в списке s pos, # позиция текущей точки в текущем цикле s[i] c, # текущий формируемый цикл, который после окончания # его формирования добавляется к списку t x; # служебная переменная (элемент списка при его переборе) # # Шаг 1. Соединяем первый и второй аргументы в один список # (т.е. записываем вторую подстановку после первой) s := Concatenation( s1, s2 ); # # Проверяем, что каждый цикл не содержит повторяющихся элементов # (в данной программе не проверяется, что циклы независимы) if ForAny(s, x -> Length( x ) <> Length( Set( x ) ) ) then Error("An argument do not represent a permutation !!!"); fi; # # Шаг 2. Создаем пустой список, в который в процессе расчета # будут добавляться списки, соответствующие независимым циклам # из разложения итоговой подстановки t := []; # # Шаг 3. Формируем множество точек, входящих в заданные подстановки # (другие точки мы не рассматриваем). Оно будет нужно нам для # выбора точек, которые еще не были нами рассмотрены, т.е. не входят # в уже сформированные циклы результирующей подстановки t. points := Set( Flat( s ) ); # # Шаг 4. Последовательный выбор точки p из множества еще не входящих # в запись s1*s2 точек. С выбранной точки p начинается формирование # нового цикла (его запись можно начинать с любой точки, но для # удобства мы выбираем в качестве р минимальную из таких точек). while Length(points) > 0 do # Шаг 4.1. # создаем пустой список c, в который будем записывать точки цикла # (иными словами, открываем левую скобку) c := []; # Выбор минимального p, еще не входящего в запись s1*s2 p := Minimum( points ); # записываем р в список c - это первый элемент нашего цикла Add( c, p ); # Шаг 4.2. Продолжение формирование цикла c: если на некотором шаге # его последний элемент - точка p, то добавляем к циклу c образ # точки p под действием подстановки s1*s2. Процесс продолжаем # до тех пор, пока цикл не замкнется, т.е. пока не получим первый # элемент цикла c. repeat # Шаг 4.3. Перебор циклов из списка s в обратном порядке # для определения образа точки p for i in [ Length(s), Length(s)-1 .. 1 ] do # если текущий цикл s[i] не содержит p, мы его пропускаем if p in s[i] then # иначе определяем номер точки p в цикле s[i] pos := Position( s[i], p ); if pos = Length( s[i] ) then # если точка р - последняя в цикле s[i], то она # переходит в первый его элемент p := s[i][1]; else # в противном случае она переходит в элемент цикла # с номером, на единицу большим, т.е. следующий за ней p := s[i][pos+1]; fi; fi; # если i не равняется единице, то возвращаемся на шаг 4.2, # уменьшая i на единицу (т.к. перебираем циклы справа налево) od; # в результате после шага 4.3 вместо исходного значения р # мы получили его образ под действием подстановки s1*s2. Если # этот образ совпадает с первым элементом формируемого цикла, # то цикл замкнулся (ставим правую скобку). В противном случае # добавляем этот элемент к циклу и вовзращаемся на шаг 4.2 if p <> c[1] then Add( c, p ); fi; until p = c[1]; # Добавляем полученный цикл к результирующему списку t Add( t, c ); # Теперь удаляем из списка points все точки, входящие в цикл c, # для того, чтобы затем определить, какие еще точки не были учтены SubtractSet( points, c ); # Если после этого список points еще не пуст, то возвращаемся # на шаг 4 и начинаем формирование следующего цикла od; # если же перебрали уже все возможные точки, то удаляем из # списка t циклы единичной длины, а затем возвращаем результат return Filtered( t, x -> Length( x ) > 1 ); end;

Блок-схема данной программы находится здесь.

Работу программы можно усовершенствовать, сделав ее более наглядной. Конечно, несложно было бы просто вставить в нее промежуточную печать результатов. Однако, мы продемонстрируем другой подход, позволяющий управлять объемом информации, выводимой на экран, без последующего внесения изменений в программу. Для этого нужно ввести команду

DeclareInfoClass("MyInfo");

Эта команда определяет так называемый InfoClass под именем "MyInfo". Ему соответствует уровень вывода информации, который называется InfoLevel. По умолчанию InfoLevel для вновь созданного класса равен нулю, и никакие информационные сообщения не печатаются. Далее, для печати информационных сообщений в программу включаются строки вида
Info( MyInfo, i, "text", variable );

Если теперь ввести, например, команду

SetInfoLevel(MyInfo,1);

то при этом все информационные сообщения, у которых параметр i не будет превышать 1, будут выдавать информацию на экран, а сообщения с большим значением параметра i будут игнорироваться.

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

gap> Read("prodperm.g");

для включения режима печати информационных сообщений нужно ввести команду

gap> SetInfoLevel(MyInfo,1);

Тогда работа с подстановками будет выглядеть так:

gap> ProductOfTwoPermutations([[2,3,5,4],[1,6]], [[1,3,5]]); Starting from 1 ( 1 cycle 3 : 1 -> 3 cycle 1 : 3 -> 5 ( 1 5 cycle 3 : 5 -> 1 cycle 2 : 1 -> 6 ( 1 5 6 cycle 2 : 6 -> 1 ( 1 5 6 ) Starting from 2 ( 1 5 6 )( 2 cycle 1 : 2 -> 3 ( 1 5 6 )( 2 3 cycle 3 : 3 -> 5 cycle 1 : 5 -> 4 ( 1 5 6 )( 2 3 4 cycle 1 : 4 -> 2 ( 1 5 6 )( 2 3 4 ) [ [ 1, 5, 6 ], [ 2, 3, 4 ] ]

Эти и

нформационные сообщения показывают следующую информацию:

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

Полезным упражнением будет изучение текста программы prodperm.g и сопоставление шаго алгоритма и выводимых на печать информационных сообщений.

Для изучения алгоритма умножения подстановок в виде произведения циклов предлагаем ознакомиться также с презентацией в MS PowerPoint, показывающую его на примере. Вы можете загрузить презентацию здесь. Если же у Вас не установлен MS PowerPoint, то Вы можете загрузить изображение в формате WMF здесь.

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