188
правок
Изменения
Нет описания правки
__TOC__
== Действие перестановки на набор элементов ==
{{Определение
|definition=
Пусть <tex>\pi</tex> {{---}} перестановка порядка <tex>n</tex>, и <tex>\{a_i\}</tex> {{---}} множество некоторых объектов, занумерованных числами от одного до <tex>n</tex>. Тогда '''результатом действия перестановки ''' на этот набор объектов назовём множество объектов <tex>\{b_i\}</tex>, занумерованных числами от одного до <tex>n</tex>, причём <tex>b_i = a_{\pi_i}</tex>.
}}
{{Определение
|neat = 1
|definition='''Степенью перестановки ''' называется минимальное число <tex>n \in N</tex> такое, что <tex>\pi^n = i</tex>}}
{{Утверждение
|statement=
Если длины всех циклов не превышают <tex>2</tex>, то перестановка является [[Умножение_перестановок,_обратная_перестановка,_группа_перестановок#def_involution | инволюцией]].
|proof=
Действительно, в таком случае по вышеупомянутому <tex>\pi^2 = i</tex>. Домножив на <tex>\pi^{-1}</tex> получим <tex>\pi^{-1} = \pi</tex>.
}}
==Поиск всех циклов в перестановке==
{{Задача
|definition=Дана перестановка <tex>\pi</tex> порядка <tex>n</tex>, требуется найти все циклы в ней. }}
Рассмотрим элемент перестановки <tex>\pi_i</tex>. Добавим его к циклу, отметим позицию <tex>i</tex> посещенной и перейдем к <tex>\pi_{\pi_i}</tex>. Если мы перешли в позицию <tex>i</tex>, которую уже посещали, значит мы нашли очередной цикл перестановки. Перейдем к первой непосещенной позиции и продолжим поиск.
Рассмотрим в качестве примера поиск циклов в перестановке <tex>\langle2, 4, 5, 1, 3\rangle</tex>:
# В позиции <tex>1</tex> находится число <tex>2</tex>. Добавим его к новому циклу и перейдем в позицию <tex>2</tex>. Аналогично добавим к циклу числа <tex>4</tex> и <tex>1</tex>. Перейдем в позицию <tex>1</tex>, которую мы уже посещали {{---}} нашли первый цикл <tex>(2, 4, 1)</tex>.
# Аналогично найдем второй цикл <tex>(5, 3)</tex>.
# Таким образом, <tex>(2, 4, 1)(5, 3)=\langle2, 4, 5, 1, 3\rangle</tex>
===Псевдокод алгоритма===
<code>
'''vector<bool>''' used(n) ''<font color="green">// массив, где отмечены посещенные позиции</font>''
'''for''' i = 1 '''to''' n
'''if''' '''not''' used[i]
j = i
'''vector<int>''' cycle
'''while''' '''not''' used[j]
cycle.push_back(p[j])
used[j] = true
j = p[j]
'''print''' cycle ''<font color="green">// распечатаем очередной цикл перестановки</font>''
</code>
==См. также==
*[[Действие группы на множестве]]
== Источники ==
* [httphttps://ru.wikipedia.org/wiki/%CFD0%9F%D0%E5B5%F0D1%E580%F1D0%F2B5%E0D1%ED81%EED1%E282%EAD0%E0 B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0 Википедия{{---}} Перестановка]* [https: Перестановки//en.wikipedia.org/wiki/Permutation Wikipedia {{---}} Permutation]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
