Действие перестановки на набор из элементов, представление в виде циклов

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Действие перестановки на набор элементов

Определение:

Пусть [math]\pi[/math] — перестановка из [math]n[/math] элементов, и [math]\{a_i\}[/math] — множество некоторых объектов, занумерованных числами от [math]1[/math] до [math]n[/math]. Тогда результатом действия перестановки на этот набор объектов назовём множество объектов [math]\{b_i\}[/math], занумерованных числами от одного до [math]n[/math], причём [math]b_i = a_{\pi_i}[/math].

Обозначим за [math]A[/math] множество (не пронумерованных) объектов [math]\{a_1, \dots, a_n\}[/math]. Поскольку перестановку можно рассматривать как отображение [math]\pi \colon \{1, \dots, n\} \to \{a_1, \dots, a_n\}[/math], а нумерацию как отображение [math]\alpha \colon \{1, \dots, n\} \to A[/math], то действие перестановки можно определить как композицию отображений [math]\alpha \circ \pi[/math].

Например, рассмотрим множество [math]A = (a, b, c, d)[/math] и перестановку [math]\pi = \langle 3, 4, 1, 2 \rangle[/math]. Тогда результат действия [math]\pi[/math] на [math]A[/math] — упорядоченное множество [math]\pi(A) = (c, d, a, b)[/math]. Если рассмотреть граф перестановки (описано ниже), то действие перестановки можно представить таким образом: каждый элемент устанавливается в вершину графа, соответствующую номеру этого элемента, после чего каждый элемент передвигается по исходящему из этой вершины ребру.

Иллюстрация действия перестановки

Также, композицию перестановок можно выразить как действие одной перестановки на другую. Стоит отметить, что действие перестановки [math]\pi^n[/math] соответствует переходу по графу [math]n[/math] раз.

Действие обратной перестановки над множеством [math]A[/math] соответствует переходу элементов по развёрнутым рёбрам и даёт упорядоченное множество [math]b[/math], для которого верно [math]\pi(b) = i(A)[/math].

Утверждение:

Если [math]a = i(A), b = \pi^{-1}(A)[/math], то [math]\pi(b) = a[/math];

[math]\triangleright[/math]

Поскольку [math]b[/math] можно представить как [math]A \circ(\alpha \circ \pi^{-1})[/math], то [math]\pi(b) = (A \circ \alpha \circ \pi^{-1}) \circ \pi = A \circ \alpha \circ (\pi^{-1} \circ \pi) = A \circ \alpha = a [/math]

[math]\triangleleft[/math]

Циклы

Определение:

Циклом длины [math]~l[/math] называется такая перестановка [math]\pi,[/math] которая тождественна на всём множестве [math]X,[/math] кроме подмножества [math]\{x_1,x_2,\dots,x_l\}\subset X[/math] и [math]\pi(x_l)=x_1[/math], [math]\pi(x_i)=x_{i+1}[/math]. Обозначается [math](x_1,x_2,\dots,x_l)[/math].

Изображение перестановки в виде графа

Перестановку можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: [math](1, 5, 2)(3, 6)(4)=\langle 5,1,6,4,2,3\rangle [/math].

Цикл может быть записан по разному, например, в приведенном выше примере цикл [math](1, 5, 2)[/math] может быть записан как [math](5, 2, 1)[/math], [math](2, 1, 5)[/math], но не может быть записан как [math](2, 5, 1)[/math].

Перестановку можно представить в виде графа. Граф содержит ребро от вершины [math]x_i[/math] к вершине [math]x_j[/math] если [math]\pi(x_i) = x_j[/math]. Тогда циклы перестановки соответствуют циклическим путям в графе.

С циклами связаны некоторые интересные свойства перестановок.

Определение:

Степенью перестановки называется минимальное число [math]n \in N[/math] такое, что [math]\pi^n = i[/math]

Утверждение:

Степень перестановки равна наименьшему общему кратному длин всех циклов

[math]\triangleright[/math]

Пусть [math]k[/math] — степень перестановки. Граф перестановки разбит на циклы, и для того, чтобы какой-то элемент прошёл по своему циклу один раз, нужно возвести перестановку в степень [math]l[/math], где [math]l[/math] — длина цикла. Если элемент проходит цикл несколько раз и возвращается на своё место, то можно сделать вывод о том, что перестановка возводится в степень кратную [math]l[/math]. Тогда только в том случае, когда [math]k[/math] делится на длины всех циклов, все элементы вернутся на свои места, а наименьшее такое [math]k[/math] — это НОК длин всех циклов.

[math]\triangleleft[/math]

Утверждение:

Если длины всех циклов не превышают [math]2[/math], то перестановка является инволюцией.

[math]\triangleright[/math]

Действительно, в таком случае по вышеупомянутому [math]\pi^2 = i[/math]. Домножив на [math]\pi^{-1}[/math] получим [math]\pi^{-1} = \pi[/math].

[math]\triangleleft[/math]

Поиск всех циклов в перестановке

Задача:

Дана перестановка [math]\pi[/math] из [math]n[/math] элементов, требуется найти все циклы в ней.

Рассмотрим элемент перестановки [math]\pi_i[/math]. Добавим его к циклу, отметим позицию [math]i[/math] посещенной и перейдем к [math]\pi_{\pi_i}[/math]. Если мы перешли в позицию [math]i[/math], которую уже посещали, значит мы нашли очередной цикл перестановки. Перейдем к первой непосещенной позиции и продолжим поиск.

Рассмотрим в качестве примера поиск циклов в перестановке [math]\langle2, 4, 5, 1, 3\rangle[/math]:

1. В позиции [math]1[/math] находится число [math]2[/math]. Добавим его к новому циклу и перейдем в позицию [math]2[/math]. Аналогично добавим к циклу числа [math]4[/math] и [math]1[/math]. Перейдем в позицию [math]1[/math], которую мы уже посещали — нашли первый цикл [math](2, 4, 1)[/math].
2. Аналогично найдем второй цикл [math](5, 3)[/math].
3. Таким образом, [math](2, 4, 1)(5, 3)=\langle2, 4, 5, 1, 3\rangle[/math]

Псевдокод алгоритма

 function findCycles(int p[]):
   vector<bool> used(n)             // массив, где отмечены посещенные позиции
 
   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                  // выведем на экран очередной цикл перестановки

См. также

• Теорема Кэли

Источники

• Википедия — Перестановка
• Wikipedia — Permutation