Перед тем, как приступить к рассказу о подстановках в системе GAP, приведем необходимые теоретические сведения. Итак, пусть M={1,2,3,...,n}. Взаимно однозначное отображение множества M первых n натуральных чисел на себя называется подстановкой n-й степени. Подстановку n-й степени s можно записать в виде матрицы из двух строк и n столбцов, в которой соответствующий элемент первой строки отображается в находящийся под ним элемент второй строки (очевидно, что каждая строка такой матрицы является перестановкой из n элементов). Если x - элемент множества M, и s - подстановка, то образ элемента x под действием подстановки s обозначается s(x). Тогда умножение подстановок определяется как композиция отображений:

Далее, подстановка s называется циклом длины k, если s(a₁)=a₂, s(a₂)=a₃, ... s(a_i)=a_i+1 и s(a_k)=a₁ (разумеется, все элементы, входящие в один цикл, должны быть попарно различны). Для записи циклов используется более компактное обозначение: (a₁ a₂ a₃ ... a_k). Циклы называются независимыми, если они не содержат общих элементов. Известно, что каждую подстановку можно разложить в произведение независимых циклов. Например, подстановка (1,2,3)(4,5) переводит 1 в 2, 2 в 3, 3 в 1, 4 в 5 и 5 - в 4. Цикл длины два называется транспозицией. Каждая подстановка разлагается в произведение конечного числа транспозиций, количество которых определяет четность подстановки.

Подстановки являются стандартными объектами в системе GAP. При этом ввод и вывод подстановок производится в виде произведения независимых циклов. Максимальным числом, которое может входить в запись подстановки, является 2²⁸-1. При попытке ввести подстановку, циклы которой не являются независимыми или не являются циклами вообще, выдается сообщение об ошибке.

Примеры правильных и неправильных вариантов задания подстановок:

gap> a:=(1,2,3)(4,5); # правильное задание подстановки
(1,2,3)(4,5)
gap> a:=(1,2,3,1)(3,4,5); # первый множитель - не цикл
Permutation: cycles must be disjoint and duplicate-free
gap> a:=(1,2,3)(3,4,5); # циклы не являются независимыми
Permutation: cycles must be disjoint and duplicate-free
gap> b:=(1,2,3)*(3,4,5); # так нужно поступать, если циклы не независимы
(1,2,4,5,3) # (в этом случае выполняется их умножение)
gap> e:=(); # так задается тождественная подстановка
()

Следует обратить внимание на то, что в 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)).

Если i^p не совпадает с i, то мы говорим, что i перемещается подстановкой p. В противном случае точка i называется неподвижной (или фиксированной) точкой относительно подстановки p. Прообраз точки i относительно подстановки p записывается как i/p, что позволяет быстро определить его без непосредственного вычисления подстановки, обратной к p:

gap> 1^a;
2
gap> 3^a;
1
gap> 3/a;
2
gap> 3/a=3^(a^-1); # проверим, что оба способа дают одинаковый результат
true

Приведем еще несколько примеров действий над подстановками:

gap> c:=(1,2,4)(7,3,6)(8,9); # зададим подстановку, состоящую из трех циклов
(1,2,4)(3,6,7)(8,9)
gap> b*c; # и умножим ее на b
(1,4,5,6,7,3,2)(8,9)
gap> (1,2,3)^-1; # так находят обратную подстановку
(1,3,2)
gap> (1,2,3)^(1,2); # а так - подстановку, сопряженную с данной
(1,3,2)
gap> (1,2,3)^(1,2)=(1,2)^1 * (1,2,3) * (1,2); # проверим это, вычислив сопряженную подстановку
true
gap> b/c; # так можно быстро вычислить b*c^-1
(3,4,5,7,6)(8,9)
gap> b*c^-1; # проверим это, сравнив два последних результата
(3,4,5,7,6)(8,9)

Полезными также являются функция LeftQuotient(elm1,elm2), возвращающая произведение elm1^(-1)*elm2 (для подстановок она возвращает результат быстрее, чем непосредственное нахождение подстановки, обратной к первой подстановки и последующее умножение результата на вторую подстановку), а также функция Comm(elm1,elm2), возвращающая коммутатор elm1 и elm2, который по определению равен произведению elm1^(-1) * elm2^(-1) * elm1 * elm2 :

gap> a:= (1,3)(4,6);; b:= (1,6,5,4,3,2);;
gap> LeftQuotient( a, b );
(1,2)(3,6)(4,5)
gap> Comm( a, b );
(1,5,3)(2,6,4)

Как правило, для удобства в наименованиях функций GAP, предназначенных для работы с подстановками, слово Permutation сокращается до Perm. Например, функция IsPerm проверяет, является ли объект подстановкой:

gap> IsPerm( (1,3,4,6) );
true
gap> IsPerm( [1,3,4,6] );
false

Подстановки в GAP не принадлежат к какой-либо специфической группе подстановок. Это означает, что Вы можете работать с ними, не определяя группу подстановок, которой они принадлежат. Подстановки считаются равными, если они перемещают одно и то же множество точек, и образы соответствующих точек совпадают:

gap> (1,2,3)=(2,3,1);
true
gap> (1,2,3)(10)=(2,3,1)(11);
true
gap> (1,2,3)=(1,3,2);
false

Для перестановки элементов списка в соответствии с некоторой подстановкой используется функция Permuted:

gap> Permuted( ["a","b","c","d"], (1,4)(2,3) );
[ "d", "c", "b", "a" ]

Для изучения свойств множества точек, перемещаемых подстановкой или набором подстановок, используются функции SmallestMovedPoint, LargestMovedPoint, MovedPoints и NrMovedPoints. Аргументом этих функций может быть одна подстановка, список подстановок, или, например, группа подстановок или ее класс сопряженных элементов. Действие этих функций описывается в следующей таблице.

	Аргумент - подстановка	Аргумент - набор подстановок
SmallestMovedPoint	Возвращает наименьшее положительное число, которое перемещается данной подстановкой, если такое число существует, и infinity, если подстановка является тождественной	Возвращает наименьшее значение из всех SmallestMovedPoint для элементов из данного набора подстановок, и infinity, если набор является пустым
LargestMovedPoint	Возвращает наибольшее положительное число, которое перемещается данной подстановкой, если такое число существует, и 0, если подстановка является тождественной	Возвращает наибольшее значение из всех LargestMovedPoint для элементов из данного набора подстановок, и 0, если набор является пустым
MovedPoints	Возвращает множество положительных чисел, которые перемещаются данной подстановкой.	Возвращает множество положительных чисел, которые перемещаются хотя бы одной подстановкой из данного набора
NrMovedPoints	Возвращает количество положительных чисел, которые перемещаются данной подстановкой	Возвращает количество положительных чисел, которые перемещаются хотя бы одной подстановкой из данного набора

Пример:

gap> SmallestMovedPointPerm((4,5,6)(7,2,8));
2
gap> LargestMovedPointPerm((4,5,6)(7,2,8));
8
gap> NrMovedPointsPerm((4,5,6)(7,2,8));
6
gap> MovedPoints([(2,3,4),(7,6,3),(5,47)]);
[ 2, 3, 4, 5, 6, 7, 47 ]
gap> NrMovedPoints([(2,3,4),(7,6,3),(5,47)]);
7
gap> SmallestMovedPoint([(2,3,4),(7,6,3),(5,47)]);
2
gap> LargestMovedPoint([(2,3,4),(7,6,3),(5,47)]);
47
gap> LargestMovedPoint([()]);
0
gap> SmallestMovedPoint(());
infinity

Функция SignPerm возвращает знак подстановки, который равен (-1)^k, где k - количество циклов четной длины в разложении подстановки в произведение независимых циклов (цикл четной длины представляется в виде произведения нечетного числа транспозиций, а нечетной длины - в виде четного числа транспозиций). Таким образом, знак подстановки равен 1, если она четная, и -1, если она нечетная. Знак подстановки является гомоморфизмом из симметрической группы подстановой в мультипликативную группу { +1, -1 }, ядром которого является знакопеременная группа.

gap> SignPerm((1,2,3)(4,5));
-1

Количество циклов каждой длины в разложении подстановки возвращает функция CycleStructurePerm. Ее результатом является список, i-й элемент которого содержит количество циклов длины i+1. Если подстановка не содержит циклов длины i+1, то i-й элемент списка не определен. Циклы длины 1 игнорируются. Например:

gap> CycleStructurePerm( (1,8)(2,4)(3,5,6));
[ 2, 1 ]
gap> CycleStructurePerm((1,2,3)(4,5,9,7,8));
[ , 1,, 1 ]

Кроме задания подстановок в виде произведения независимых циклов, существуют различные способы конвертации подстановок в списки и наоборот. Функция ListPerm(perm) возвращает список, который содержит образы положительных чисел под действием подстановки perm, т.е. list[i] = i^perm, где i изменяется от 1 до LargestMovedPoint(perm). Иными словами, для подстановки, заданной в виде произведения циклов, она возвращает нижнюю строку из ее представления в виде двустрочной матрицы.

Обратной к этой функции является PermList(list), которая возвращает подстановку, которая действует в соответствии со списком list. Иными словами, i^perm = list[i], если i находится в границах от 1 до длины списка list, и i^perm = i, если i больше его длины. Эта функция возвращает fail, если заданный список не определяет подстановку (например, не является плотным, содержит одинаковые числа, содежит целое число не из интервала [ 1 .. Length( list ) ] или содержит элемент, который не является целым числом.

Если src и dst - два списка положительных чисел одинаковой длины, и каждый из них не содержит одинаковых элементов, то функция MappingPermListList ( src, dst ) возвращает подстановку perm, такую что src[i]^perm = dst[i]. При этом perm оставляет на месте все числа, превышающие максимальное из чисел, входящих в списки src и dst.

Функция RestrictedPerm( perm, list ) возвращает новую подстановку, которая является ограничением подстановки perm на список list, т.е. действует на элементы списка list таким же образом, как и исходная подстановка perm, и фиксирует все точки, не входящие в список list. Список list должен быть замкнут относительно действия подстановки perm, т.е. вместе с каждым элементом i содержать его образ i^perm.

Пример:

gap> ListPerm((3,4,5));
[ 1, 2, 4, 5, 3 ]
gap> PermList([1,2,4,5,3]);
(3,4,5)
gap> MappingPermListList([2,5,1,6],[7,12,8,2]);
(1,8,5,12,11,10,9,6,2,7,4,3)
gap> RestrictedPerm((1,2)(3,4),[3..5]);
(3,4)

Группы, порожденные подстановками, задаются с помощью указания их порождающих элементов. Зададим группу, порождаемую двумя подстановками:

Как известно, это - симметрическая группа подстановок 8-й степени. Теперь вычислим ее коммутант (который является знакопеременной группой подстановок 8-й степени), найдем его порядок и установим, будет ли он коммутативным: