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

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

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

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

Для изучения алгоритма умножения подстановок справа налево приведем пример программы на языке GAP. Эта программа работает с подстановками, заданными в виде произведения независимых циклов в формате [[a1,a2,...,ai],[b1,b2,...,bj],...,[z1,z2,...,zk]]. Мы вводим свою запись подстановок, отличную от принятой в 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 здесь.

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

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