Взаимно однозначная функция называется подстановкой на . Если множество конечно (), то можно считать, что . В этом случае подстановку удобно задавать таблицей из двух строк. В первой строке – значения аргументов, во второй – соответствующее значение функции. Ниже приведены примеры произвольных дискретных подстановок и :
, .
Произведением подстановок и называется их суперпозиция . Суперпозиция – это результат последовательного применения двух подстановок. Произведение двух приведенных выше подстановок равно
.
Для вычисления результата был использован следующий алгоритм. Первый по номеру элемент подстановки равен 5. Поэтому обращаемся к пятому по номеру элементу подстановки и видим, что он также равен 5. Значит, первый элемент произведения будет равен 5.
Второй элемент равен 2. Поэтому обращаемся ко второму элементу и видим, что он равен 1. Последнее значение принимаем в качестве второго элемента произведения . Действуя аналогичным образом, получаем все оставшиеся элементы произведения.
Как можно видеть произведение подстановок также является подстановкой. Произведение подстановок определено для подстановок одинакового размера. Произведение подстановок в общем случае не обладает свойством коммутативности, то есть
.
Единичная (или тождественная) подстановка – это подстановка такая, что . Например:
.
Обратная подстановка по отношению к подстановке – это подстановка, удовлетворяющая соотношению:
. (7.8)
Таблицу обратной подстановки можно получить, если просто поменять местами строки таблицы исходной подстановки. Например:
, .
Подстановки можно представлять в графической форме, проводя стрелки от каждого элемента к элементу .
Пример 7.8. Задана постановка
.
Графическое представление этой подстановки показано на рис. 7.2.
Рис. 7.2
В современной математике алгебраические операции применяют не только к скалярным числам, но и к другим объектам. Например, к матрицам или подстановкам. Множества различных объектов, для которых определены соответствующие алгебраические операции, называются алгебрами в широком смысле этого слова. Если определены четыре действия: сложение, вычитание, умножение и деление – такая алгебра называется полем.
Таким образом, обычная алгебра (в узком смысле этого слова) является полем. Если операция деления в алгебре не определена, такая алгебра называется кольцом. Если определена только одна операция, то алгебра называется группой. Причем, эта операция должна обладать свойством ассоциативности:
,
сама алгебра должна иметь единичный элемент со свойством:
,
и для каждого объекта иметь обратный элемент :
.
Теперь мы можем утверждать, что множество подстановок образуют группу относительно операции суперпозиции. Эта группа называется симметрической степени n.
Цикл – это последовательность элементов , такая что
Цикл длины 2 называется транспозицией.
Если принять соглашение, что элементы верхней строки (аргументы) всегда располагаются в определенном порядке (например, по возрастанию), то верхнюю строку можно не указывать – подстановка однозначно определяется нижней строкой. Такие подстановки в одну строку называются перестановками. Перестановку элементов будем обозначать , где все – различные числа из диапазона .
Если в перестановке для элементов и имеет место неравенство при , то пара называется инверсией. Обозначим – число инверсий в перестановке .
Теорема 7.5. Произвольную подстановку можно представить в виде суперпозиции транспозиций соседних элементов.
Доказательство. Пусть . Переставим 1 на первое место, меняя ее местами с соседними слева элементами. Обозначим последовательность этих транспозиций через . При этом все инверсии, в которых участвовала 1, пропадут. Затем переставим 2 на второе место и т.д. Таким образом, и по свойству группы , причем .
Следствие. Всякая сортировка может быть выполнена перестановкой соседних элементов.
Такой метод сортировки известен как пузырьковый метод. Этот метод прост, но является далеко не самым эффективным алгоритмом сортировки.