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

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

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

Пусть [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