Подстановки

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

, .

Произведением подстановок и называется их суперпозиция . Суперпозиция – это результат последовательного применения двух подстановок. Произведение двух приведенных выше подстановок равно

.

Для вычисления результата был использован следующий алгоритм. Первый по номеру элемент подстановки равен 5. Поэтому обращаемся к пятому по номеру элементу подстановки и видим, что он также равен 5. Значит, первый элемент произведения будет равен 5.

Второй элемент равен 2. Поэтому обращаемся ко второму элементу и видим, что он равен 1. Последнее значение принимаем в качестве второго элемента произведения . Действуя аналогичным образом, получаем все оставшиеся элементы произведения.

Как можно видеть произведение подстановок также является подстановкой. Произведение подстановок определено для подстановок одинакового размера. Произведение подстановок в общем случае не обладает свойством коммутативности, то есть

.

Единичная (или тождественная) подстановка – это подстановка такая, что . Например:

.

Обратная подстановка по отношению к подстановке – это подстановка, удовлетворяющая соотношению:

. (7.8)

Таблицу обратной подстановки можно получить, если просто поменять местами строки таблицы исходной подстановки. Например:

, .

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

Пример 7.8. Задана постановка

.

Графическое представление этой подстановки показано на рис. 7.2.

Рис. 7.2

В современной математике алгебраические операции применяют не только к скалярным числам, но и к другим объектам. Например, к матрицам или подстановкам. Множества различных объектов, для которых определены соответствующие алгебраические операции, называются алгебрами в широком смысле этого слова. Если определены четыре действия: сложение, вычитание, умножение и деление – такая алгебра называется полем.

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

,

сама алгебра должна иметь единичный элемент со свойством:

,

и для каждого объекта иметь обратный элемент :

.

Теперь мы можем утверждать, что множество подстановок образуют группу относительно операции суперпозиции. Эта группа называется симметрической степени n.

Цикл – это последовательность элементов , такая что

Цикл длины 2 называется транспозицией.

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

Если в перестановке для элементов и имеет место неравенство при , то пара называется инверсией. Обозначим – число инверсий в перестановке .

Теорема 7.5. Произвольную подстановку можно представить в виде суперпозиции транспозиций соседних элементов.

Доказательство. Пусть . Переставим 1 на первое место, меняя ее местами с соседними слева элементами. Обозначим последовательность этих транспозиций через . При этом все инверсии, в которых участвовала 1, пропадут. Затем переставим 2 на второе место и т.д. Таким образом, и по свойству группы , причем .

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

Такой метод сортировки известен как пузырьковый метод. Этот метод прост, но является далеко не самым эффективным алгоритмом сортировки.