15
правок
Изменения
добавлена часть англ. терминов, исправлен псевдокод, ВСЕ цифры и переменные отныне добавлены в tex, добавлен пример группы подстановок
|definition=
'''Обратнойперестановкой''' перестановкой (англ. an inverse permutation) <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:
<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>
===Получение обратной перестановки===
Пусть в массиве <tex>p[i] </tex> содержится перестановка, тогда в массиве op<tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка. '''fun''' reversePerm(p : '''int[]''', rep : '''int[]''') '''int''' n = p.size; '''for(''' i = 0; i < '''to''' n; i++) '''for(''' j = 0; j < '''to''' n; j++) '''if(''' p[j] == i + 1) op rep[i] = j + 1;
При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.
<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>
Отсюда следует более эффективный алгоритм (приведена in, где <tex> visited[] </tex> -place версия)массив посещённых элементов: '''fun''' reversePerm (visited : '''boolean[] visited = new boolean''', p : '''int[]''', rep : '''int[]''') '''int''' n]= p.size; '''for (int ''' i = 0; i < '''to''' n; ++i) '''if (''' visited[i]) '''continue'''; // Reverse the cycle starting at инвертировать цикл, начинающийся в позиции <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;
==Группа перестановок==
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <tex> S_n </tex>).
|proof=
Свойства <tex>1 </tex> и <tex>3 </tex> доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>).
}}
{{Определение
|definition=
'''Группа чётных перестановок''' (англ. alternating group)<tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится.
}}
}}
==ПодстановкаГруппа подстановок==
{{Определение
}}
Всякая подстановка <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_{k_i} </tex> обозначается то число, в которое при подстановке <tex> A </tex> переходит число <tex> q_i </tex>.
{{Определение
|definition=
'''Группой подстановок''' (англ. group of substitutions) называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве.
}}
