693
правки
Изменения
→Псевдокод алгоритма
__TOC__
== Действие перестановки на набор элементов ==
{{Определение
|definition=
Пусть <tex>\pi</tex> {{---}} перестановка порядка из <tex>n</tex>элементов, и <tex>\{a_i\}</tex> {{---}} множество некоторых объектов, занумерованных числами от одного <tex>1</tex> до <tex>n</tex>. Тогда '''результатом действия перестановки ''' на этот набор объектов назовём множество объектов <tex>\{b_i\}</tex>, занумерованных числами от одного до <tex>n</tex>, причём <tex>b_i = a_{\pi_i}</tex>.
}}
Обозначим за <tex>A</tex> множество (не пронумерованных) объектов <tex>\{a_1, \dots, a_n\}</tex>. Поскольку перестановку можно рассматривать как отображение <tex>\pi \colon \{1, \dots, n\} \to \{a_1, \dots, a_n\}</tex>, а нумерацию как отображение <tex>\alpha \colon \{1, \dots, n\} \to A</tex>, то [[Файл:Permutation_action.png|400px|thumbДействие_группы_на_множестве|right|Иллюстрация действия действие перестановки]]можно определить как композицию отображений <tex>\alpha \circ \pi</tex>.
Также, композицию перестановок можно выразить как действие одной перестановки на другую.
Стоит отметить, что действие перестановки <tex>\pi^n</tex> соответствует переходу по графу <tex>n</tex> раз.
==Циклы==
Цикл может быть записан по разному, например, в приведенном выше примере цикл <tex>(1, 5, 2)</tex> может быть записан как <tex>(5, 2, 1)</tex>, <tex>(2, 1, 5)</tex>, но не может быть записан как <tex>(2, 5, 1)</tex>.
Перестановку можно представить в виде [[Основные_определения_теории_графов|графа]]. Граф содержит ребро от вершины <tex>x_i</tex> к вершине <tex>x_j</tex> если <tex>\pi(x_i) = x_j</tex>. Тогда циклы перестановки соответствуют циклическим путям в графе.
С циклами связаны некоторые интересные свойства перестановок.
{{Определение
{{Утверждение
|statement=
Степень перестановки равна наименьшему общему кратному длин всех циклов
|proof=Пусть <tex>k</tex> — степень перестановки. Граф перестановки разбит на циклы, и для того, чтобы какой-то элемент прошёл по своему циклу один раз, нужно возвести перестановку в степень <tex>l</tex>, где <tex>l</tex> — длина цикла. Если элемент проходит цикл несколько раз и возвращается на своё место, то можно сделать вывод о том, что перестановка возводится в степень кратную <tex>l</tex>. Тогда только в том случае, когда <tex>k</tex> делится на длины всех циклов, все элементы вернутся на свои места, а наименьшее такое <tex>k</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> ===Псевдокод алгоритма=== '''function''' findCycles('''int''' p[]): '''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>'' ==См. также==*[[Теорема Кэли]]
== Источники ==
* [httphttps://ru.wikipedia.org/wiki/%CFD0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%E5B0%F0D0%E5BD%F1D0%F2BE%E0D0%EDB2%EED0%E2BA%EAD0%E0 B0 Википедия{{---}} Перестановка]* [https://en.wikipedia.org/wiki/Permutation Wikipedia {{---}} Permutation]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]