Перестановка — это отображение __TOC__== Действие перестановки на набор элементов == {{Определение|definition=Пусть <mathtex>\pi:X</tex> {{---}} перестановка из <tex>n</tex> элементов, и <tex>\{a_i\}</tex> {{---}} множество некоторых объектов, занумерованных числами от <tex>1</tex> до <tex>n</tex>. Тогда '''результатом действия перестановки''' на этот набор объектов назовём множество объектов <tex>\{b_i\rightarrow X}</tex>, занумерованных числами от одного до <tex>n</mathtex>, которое каждому причём <mathtex>x_i b_i = a_{\in Xpi_i}</tex>.}} Обозначим за <tex>A</mathtex> ставит во взаимно-однозначное соответствие множество (не пронумерованных) объектов <mathtex>x_j \in X{a_1, \dots, a_n\}</mathtex>. Индексы Поскольку перестановку можно рассматривать как отображение <tex>\pi \colon \{1, \dots, n\} \to \{a_1, \dots, a_n\}<math/tex>i,j а нумерацию как отображение <tex>\alpha \in colon \mathcal{f1, \dots, n\}\to A</tex>, то [[Действие_группы_на_множестве|действие перестановки]] можно определить как композицию отображений <tex>\alpha \circ \pi</tex>. Например, рассмотрим множество <tex>A = (a, b, c, d)</tex> и перестановку <tex>\pi = \langle 3, 4, 1, 2\rangle</tex>. Тогда результат действия <tex>\pi</tex> на <tex>A</tex> {{---}} упорядоченное множество <tex>\pi(A) = (c, d, a, b)</tex>. Если рассмотреть [[Основные_определения_теории_графов|граф]] перестановки (описано ниже), то действие перестановки можно представить таким образом: каждый элемент устанавливается в вершину графа, соответствующую номеру этого элемента, после чего каждый элемент передвигается по исходящему из этой вершины ребру. [[Файл:Permutation_action.png|400px|frame|center|Иллюстрация действия перестановки]] Также, композицию перестановок можно выразить как действие одной перестановки на другую.Стоит отметить, что действие перестановки <tex>\pi^n</tex> соответствует переходу по графу <tex>n</tex> раз. Действие обратной перестановки над множеством <tex>A</tex> соответствует переходу элементов по развёрнутым рёбрам и даёт упорядоченное множество <tex>b</tex>, для которого верно <tex>\ldotspi(b) = i(A)</tex>.{{Утверждение|statement=Если <tex>a = i(A), b = \pi^{-1}(A)</tex>, nто <tex>\pi(b) = a</tex>;|proof=Поскольку <tex>b</tex> можно представить как <tex>A \circ(\alpha \circ \mathcalpi^{g-1})</mathtex>, где то <tex>\pi(b) = (A \circ \alpha \circ \pi^{-1}) \circ \pi = A \circ \alpha \circ (\pi^{-1} \circ \pi) = A \circ \alpha = a <math/tex>n }} ==Циклы=={{Определение|definition= '''Циклом''' длины <tex>~l</tex> называется такая перестановка <tex>\pi,</tex> которая тождественна на всём множестве <tex>X,</tex> кроме подмножества <tex>\mathcal{jx_1,x_2,\dots,x_l\}\subset X</tex> и <tex>\pi(x_l)=x_1</tex>, <tex>\mathcalpi(x_i)=x_{ji+1}</mathtex>.Число Обозначается <mathtex>~n(x_1,x_2,\dots,x_l)</mathtex> называют порядком .}}[[Файл:cycles.gif|150px|right|frame|Изображение перестановки. в виде графа]]Перестановку можно записать в виде упорядоченного набора из чисел произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: <mathtex>(1, 5, 2)(3,6)(4)=\ldotslangle 5,1,6,4,2, n3\rangle </mathtex>.Элемент набора Цикл может быть записан по разному, например, в приведенном выше примере цикл <mathtex>~a_k(1, 5, 2)</tex> может быть записан как <tex>(5, 2, 1)</tex>, <tex>(2, 1, 5)</mathtex>, но не может быть записан как <tex> означает(2, что 5, 1)</tex>. Перестановку можно представить в виде [[Основные_определения_теории_графов|графа]]. Граф содержит ребро от вершины <tex>x_i</tex> к вершине <tex>x_j</tex> если <mathtex>~\pi (x_x_i) = x_j</tex>. Тогда циклы перестановки соответствуют циклическим путям в графе. С циклами связаны некоторые интересные свойства перестановок.{{a_kОпределение|definition='''Степенью перестановки''' называется минимальное число <tex>n \in N</tex> такое, что <tex>\pi^n = i</tex>}) } {{Утверждение|statement=Степень перестановки равна наименьшему общему кратному длин всех циклов|proof= x_k Пусть <tex>k</tex> — степень перестановки. Граф перестановки разбит на циклы, и для того, чтобы какой-то элемент прошёл по своему циклу один раз, нужно возвести перестановку в степень <tex>l</mathtex>, где <tex>l</tex> — длина цикла. Таким образомЕсли элемент проходит цикл несколько раз и возвращается на своё место, то можно сделать вывод о том, если что перестановка возводится в степень кратную <mathtex> l<x_1/tex>. Тогда только в том случае,x_{2}когда <tex>k</tex> делится на длины всех циклов,\ldotsвсе элементы вернутся на свои места,x_{n}а наименьшее такое <tex>k</mathtex> — упорядоченный набор элементов из множестваэто НОК длин всех циклов. }} {{Утверждение|statement=Если длины всех циклов не превышают <mathtex>~X2</mathtex>, то перестановка является [[Умножение_перестановок,_обратная_перестановка,_группа_перестановок#def_involution | инволюцией]].|proof=Действительно, в таком случае по вышеупомянутому <mathtex>\pi (^2 = i</tex>. Домножив на <x_tex>\pi^{-1},x_</tex> получим <tex>\pi^{2-1},= \ldots,x_{npi</tex>. }}>) ==Поиск всех циклов в перестановке== <x_{q_1},x_{q_2},Задача|definition=Дана перестановка <tex>\ldotspi</tex> из <tex>n</tex> элементов,x_{q_nтребуется найти все циклы в ней. }}Рассмотрим элемент перестановки <tex> \pi_i</mathtex>. Добавим его к циклу, где отметим позицию <tex>i</tex> посещенной и перейдем к <mathtex>q_\pi_{a_i\pi_i} = </tex>. Если мы перешли в позицию <tex>i</mathtex>, которую уже посещали, значит мы нашли очередной цикл перестановки. Перейдем к первой непосещенной позиции и продолжим поиск. Например Рассмотрим в качестве примера поиск циклов в перестановке <tex>\langle2, 4, 5, 1, применив перестановку 3\rangle</tex>: # В позиции <tex>1</tex> находится число <tex>2</tex>. Добавим его к новому циклу и перейдем в позицию <tex>2</tex>. Аналогично добавим к циклу числа <tex>4</tex> и <tex>1</tex>. Перейдем в позицию <mathtex>~1<3/tex>,которую мы уже посещали {{---}} нашли первый цикл <tex>(2,4,1)</tex>.# Аналогично найдем второй цикл <tex>(5, 3)</mathtex> к набору элементов .# Таким образом, <mathtex>~(x_12,x_24,x_31)(5,x_43)=\langle2, 4, 5, 1, 3\rangle</mathtex> ===Псевдокод алгоритма=== <code> '''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 ''<mathfont color="green">~// распечатаем очередной цикл перестановки<x_4,x_2,x_1,x_3/font>''</mathcode> ==См. также==*[[Теорема Кэли]] == Источники ==* [https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0 Википедия {{---}} Перестановка]* [https://en.wikipedia.org/wiki/Permutation Wikipedia {{---}} Permutation] [[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика ]]
