Изменения

Перейти к: навигация, поиск
Псевдокод алгоритма
'''Перестановка''' — это отображение <tex>\pi:X\rightarrow X</tex>, которое каждому <tex>x_i \in X</tex> ставит во взаимно-однозначное соответствие <tex>x_j \in X</tex>
Индексы __TOC__== Действие перестановки на набор элементов == {{Определение|definition=Пусть <tex>i,j \in \mathcalpi</tex> {{f---}1, 2} перестановка из <tex>n</tex> элементов, и <tex>\ldots, n{a_i\mathcal}</tex> {{g---}}множество некоторых объектов, занумерованных числами от <tex>1</tex>, где до <tex>n = </tex>. Тогда '''результатом действия перестановки''' на этот набор объектов назовём множество объектов <tex>\mathcal{j}Xb_i\mathcal{j}</tex>.Число , занумерованных числами от одного до <tex>~n</tex> называют порядком перестановки. Перестановку можно записать в виде упорядоченного набора из чисел , причём <tex>1, 2,b_i = a_{\ldots, npi_i}</tex>.Элемент такого набора }} Обозначим за <tex>A</tex> множество (не пронумерованных) объектов <tex>~\mathcal{h}a_1,a_2,\ldotsdots,a_n\mathcal{i}~ a_k</tex> означает, что . Поскольку перестановку можно рассматривать как отображение <tex>~\pi (x_\colon \{1, \dots, n\} \to \{a_ka_1, \dots, a_n\}) = x_k </tex>. Таким образом, если а нумерацию как отображение <tex> \Theta = alpha \colon \mathcal{h}x_1,x_{2}1,\ldotsdots,x_{n\}\mathcal{i}to A</tex> — упорядоченный набор элементов из множества, то [[Действие_группы_на_множестве|действие перестановки]] можно определить как композицию отображений <tex>~X\alpha \circ \pi</tex>. Например, рассмотрим множество <tex>A = (a, b, c, то d)</tex> и перестановку <tex>\pi (\Theta) = \mathcal{h}x_{q_1}langle 3,x_{q_2}4,\ldots1,x_{q_n}2 \mathcal{i} rangle</tex>, где . Тогда результат действия <tex>q_{a_i} = i\pi</tex>. Например, применив перестановку на <tex>~\mathcal{h}3,2,4,1\mathcal{i}A</tex> к набору элементов {{---}} упорядоченное множество <tex>~\pi(A) = (x_1c,x_2d,x_3a,x_4b)</tex>. Если рассмотреть [[Основные_определения_теории_графов|граф]] перестановки (описано ниже), то действие перестановки можно представить таким образом: каждый элемент устанавливается в вершину графа, соответствующую номеру этого элемента, после чего каждый элемент передвигается по исходящему из этой вершины ребру. [[Файл:Permutation_action.png|400px|frame|center|Иллюстрация действия перестановки]] Также, композицию перестановок можно выразить как действие одной перестановки на другую.Стоит отметить, получим набор что действие перестановки <tex>~\mathcal{h}x_4,x_2,x_1,x_3\mathcal{i}pi^n</tex>. соответствует переходу по графу <tex>n<br\/tex>раз.==Произведение перестановок==Произведением перестановок Действие обратной перестановки над множеством <tex>~\piA</tex> соответствует переходу элементов по развёрнутым рёбрам и даёт упорядоченное множество <tex>~\sigmab</tex> называется композиция (т.е. последовательное применение) этих перестановок: , для которого верно <tex>(\pi*\sigma(b)= i(\ThetaA)</tex>.{{Утверждение|statement=Если <tex>a = i(A) , b = \pi^{-1}(\sigma(\ThetaA)) = </tex>, то <tex>\pi \circ \sigma (\Thetab)= a</tex>.;|proof=Легко показать, что произведение перестановок тоже является перестановкой, причем если Поскольку <tex>b</tex> можно представить как <tex>~A \phi = circ(\alpha \circ \pi*\sigma^{-1})</tex>, то <tex>\phipi(x_ib) = (A \circ \alpha \circ \pi ^{-1}) \circ \sigma pi = A \circ \alpha \circ (x_i\pi^{-1} \circ \pi)= A \circ \alpha = a </tex>.}} 
==Циклы==
{{Определение|definition= '''Циклом ''' длины <tex>~l</tex> называется такая перестановка <tex>~\pi,</tex> которая тождественна на всём множестве <tex>X,</tex> кроме подмножества <tex>\{x_1,x_2,\dots,x_l\}\subset X</tex> и <tex>~\pi(x_l)=x_1,</tex> , <tex>~\pi(x_i)=x_{i+1}.</tex> . Обозначается <tex>(x_1,x_2,\dots,x_l).</tex> .}}[[Файл:cycles.gif|150px|right|frame|Изображение перестановки в виде графа]]Перестановку также можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: <tex>~(1, 5, 2)(3, 6)(4)=\mathcal{h}langle 5,1,6,4,2,3\mathcalrangle </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>. Тогда циклы перестановки соответствуют циклическим путям в графе. С циклами связаны некоторые интересные свойства перестановок.{{Определение|definition='''Степенью перестановки''' называется минимальное число <tex>n \in N</tex> такое, что <tex>\pi^n = i</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> ===Псевдокод алгоритма=== <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 ''<font color="green">// распечатаем очередной цикл перестановки</font>''</code> ==См. также==*[[Теорема Кэли]] == Источники ==* [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]
Перестановку можно представить в виде графа. Граф содержит ребро от вершины <tex>~x_i</tex> к вершине <tex>~x_j</tex> если <tex>~\pi(x_j) = x_i</tex>, то есть элемент <tex>~x_i</tex> переходит в <tex>~x_j</tex> после применения перестановки <tex>~\pi</tex>. Тогда циклы перестановки соответствуют циклическим путям в графе.[[Категория: Дискретная математика и алгоритмы]][[ФайлКатегория:Циклы_мал.pngКомбинаторика ]]

Навигация