Умножение перестановок, обратная перестановка, группа перестановок — различия между версиями
Denis (обсуждение | вклад) (Как-то так оформил тикет) |
Denis (обсуждение | вклад) (добавлена часть англ. терминов, исправлен псевдокод, ВСЕ цифры и переменные отныне добавлены в tex, добавлен пример группы подстановок) |
||
Строка 41: | Строка 41: | ||
|definition= | |definition= | ||
− | '''Обратной''' | + | '''Обратной перестановкой''' (англ. an inverse permutation) <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что: |
<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex> | <tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex> | ||
Строка 90: | Строка 90: | ||
===Получение обратной перестановки=== | ===Получение обратной перестановки=== | ||
− | Пусть в массиве p[i] содержится перестановка, тогда в массиве | + | Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка. |
− | + | '''fun''' reversePerm(p : '''int[]''', rep : '''int[]''') | |
− | + | '''int''' n = p.size; | |
− | + | '''for''' i = 0 '''to''' n | |
− | + | '''for''' j = 0 '''to''' n | |
− | + | '''if''' p[j] == i + 1 | |
+ | rep[i] = j + 1; | ||
При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах. | При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах. | ||
Строка 101: | Строка 102: | ||
<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex> | <tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex> | ||
− | Отсюда следует более эффективный алгоритм | + | Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов: |
− | + | '''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''') | |
− | boolean[] | + | '''int''' n = p.size; |
− | + | '''for''' i = 0 '''to''' n | |
− | + | '''if''' visited[i] | |
− | + | '''continue'''; | |
− | + | // инвертировать цикл, начинающийся в позиции <tex> i </tex> | |
− | + | '''int''' last = i; | |
− | + | '''int''' j = p[i]; | |
− | + | '''while''' '''true''' | |
− | + | '''int''' next = p[j]; | |
− | + | p[j] = last; | |
− | + | visited[j] = '''true'''; | |
− | + | '''if''' j == i | |
− | + | '''break'''; | |
+ | last = j; | ||
+ | j = next; | ||
==Группа перестановок== | ==Группа перестановок== | ||
Строка 133: | Строка 136: | ||
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <tex> S_n </tex>). | Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <tex> S_n </tex>). | ||
|proof= | |proof= | ||
− | Свойства 1 и 3 доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>). | + | Свойства <tex>1</tex> и <tex>3</tex> доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>). |
}} | }} | ||
Строка 144: | Строка 147: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Группа чётных перестановок''' <tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится. | + | '''Группа чётных перестановок''' (англ. alternating group)<tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится. |
}} | }} | ||
Строка 154: | Строка 157: | ||
}} | }} | ||
− | == | + | ==Группа подстановок== |
{{Определение | {{Определение | ||
Строка 162: | Строка 165: | ||
}} | }} | ||
− | Всякая подстановка A может быть записана при помощи двух перестановок, подписанных одна под другой: | + | Всякая подстановка <tex>A</tex> может быть записана при помощи двух перестановок, подписанных одна под другой: |
<tex> A = \begin{pmatrix} q_1 & q_2 & ... & q_n \\ a_{k_1} & a_{k_2} & ... & a_{k_n} \end{pmatrix} </tex> | <tex> A = \begin{pmatrix} q_1 & q_2 & ... & q_n \\ a_{k_1} & a_{k_2} & ... & a_{k_n} \end{pmatrix} </tex> | ||
Где через <tex> a_{k_i} </tex> обозначается то число, в которое при подстановке <tex> A </tex> переходит число <tex> q_i </tex>. | Где через <tex> a_{k_i} </tex> обозначается то число, в которое при подстановке <tex> A </tex> переходит число <tex> q_i </tex>. | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | '''Группой подстановок''' (англ. group of substitutions) называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве. | ||
+ | |||
+ | }} | ||
Версия 22:14, 3 января 2018
Содержание
Умножение перестановок
Определение: |
Умножением (композицией) перестановок,представленных в виде целочисленных функций | , где позиция элемента, а — его номер, называется перестановка, получаемая по следующему правилу:
Утверждение: |
Умножение перестановок ассоциативно:
|
Доказывается простым раскрытием скобок. |
Пример
или
Обратная перестановка
Определение: |
Обратной перестановкой (англ. an inverse permutation) | к перестановке называется такая перестановка, что:
Определение: |
Перестановка, равная своей обратной, называется инволюцией (англ. involution): | , то есть её представление в виде циклов не содержит цикла, размер которого больше двух.
Утверждение: |
Количество инволюционных перестановок длины может быть получено по формуле: , где |
Существует | инволюций, при . Число инволюций, содержащих цикл , где , . Имеем, что
Определение: |
Перестановка, содержащая чётное количество инверсий, называется чётной, в противном случае | нечётной.
Определение: |
Перестановка, меняющая местами только два элемента, называется транспозицией (англ. transposition). |
Лемма: |
Если в перестановке, длина которой больше , поменять местами элемента, то её четность изменится. |
Доказательство: |
Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами | и находятся элементов, то есть перестановка имеет вид: . Сначала поменяем последовательно с числами , а затем число с рядом стоящими . В итоге мы выполним транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
Получение обратной перестановки
Пусть в массиве
содержится перестановка, тогда в массиве , после выполнения алгоритма, будет содержаться обратная перестановка.fun reversePerm(p : int[], rep : int[]) int n = p.size; for i = 0 to n for j = 0 to n if p[j] == i + 1 rep[i] = j + 1;
При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.
Отсюда следует более эффективный алгоритм, где
- массив посещённых элементов: fun reversePerm (visited : boolean[], p : int[], rep : int[])
int n = p.size;
for i = 0 to n
if visited[i]
continue;
// инвертировать цикл, начинающийся в позиции
int last = i;
int j = p[i];
while true
int next = p[j];
p[j] = last;
visited[j] = true;
if j == i
break;
last = j;
j = next;
Группа перестановок
Определение: |
Группой называется множество
| с заданной на нём бинарной операцией , удовлетворяющей следующим свойствам:
Утверждение: |
Множество перестановок с элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают ). |
Свойства | и доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка ( ).
Мощность симметрической группы:
Теорема Кэли утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
Группа чётных перестановок
Определение: |
Группа чётных перестановок (англ. alternating group) | является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится.
Утверждение: |
Количество чётных перестановок длины равно количеству нечётных и равно |
Пусть число число чётных перестановок | , а нечётных . Сделаем транспозицию для всех чётных перестановок. Получим нечётных различных перестановок, то есть . Проделаем то же самое с нечётными перестановками. Получим, что , то есть и .
Группа подстановок
Определение: |
Подстановкой (англ. substitution) называется всякое взаимно однозначное отображение | множества первых натуральных чисел на себя.
Всякая подстановка может быть записана при помощи двух перестановок, подписанных одна под другой:
Где через
обозначается то число, в которое при подстановке переходит число .
Определение: |
Группой подстановок (англ. group of substitutions) называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве. |
Источники и литература
- https://en.wikipedia.org/wiki/Involution_(mathematics)
- Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161