Умножение перестановок, обратная перестановка, группа перестановок — различия между версиями
(→Пример) |
|||
Строка 26: | Строка 26: | ||
===Пример=== | ===Пример=== | ||
− | <tex> \varphi(1)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 4 \end{pmatrix} </tex> | + | <tex> \varphi(1)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 4 \end{pmatrix} = (1,2,5)(3,6,4) </tex> |
− | <tex> \varphi(2)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} </tex> | + | <tex> \varphi(2)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} = (1,4,6,2)(3)(5)</tex> |
<tex> (\varphi(1)\varphi(2))_i=</tex> | <tex> (\varphi(1)\varphi(2))_i=</tex> | ||
Строка 35: | Строка 35: | ||
\begin{pmatrix} 4 & 1 & 3 & 6 & 5 & 2 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} =</tex> | \begin{pmatrix} 4 & 1 & 3 & 6 & 5 & 2 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} =</tex> | ||
<tex>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix}</tex> | <tex>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix}</tex> | ||
+ | |||
+ | или | ||
+ | |||
+ | <tex> (\varphi(1)\varphi(2))_i= (1,2,5)(3,6,4)(1,4,6,2) =(1,3,6,5)(2)(4) = (1,3,6,5) </tex> | ||
==Обратная перестановка== | ==Обратная перестановка== |
Версия 20:28, 4 января 2015
Содержание
Умножение перестановок
Определение: |
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу: |
Утверждение: |
Умножение перестановок ассоциативно:
|
Доказывается простым раскрытием скобок. |
Пример
или
Обратная перестановка
Определение: |
Обратной перестановкой | к перестановке называется такая перестановка, что:
Определение: |
Перестановка, равная своей обратной, называется инволюцией: |
Получение обратной перестановки
Пусть в массиве p[i] содержится перестановка, тогда в массиве op[i], после выполнения алгоритма, будет содержаться обратная перестановка.
for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { if(p[j] == i + 1) { op[i] = j + 1; } } }
При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.
Отсюда следует более эффективный алгоритм (приведена in-place версия):
boolean[] visited = new boolean[n]; for (int i = 0; i < n; ++i) { if (visited[i]) continue; // Reverse the cycle starting at i 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; } }
Группа перестановок
Определение: |
Группой называется множество
| с заданной на нём бинарной операцией , удовлетворяющей следующим свойствам:
Утверждение: |
Множество перестановок с элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают ). |
Свойства 1 и 3 доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка ( | ).
Мощность симметрической группы:
Теорема Кэли утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
Источники и литература
- инволюция (Wikipedia, the free encyclopedia)
- Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161