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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Циклы)
(Псевдокод алгоритма)
 
(не показано 8 промежуточных версий 4 участников)
Строка 1: Строка 1:
 +
 +
__TOC__
 
== Действие перестановки на набор элементов ==
 
== Действие перестановки на набор элементов ==
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть <tex>\pi</tex> {{---}} перестановка порядка <tex>n</tex>, и <tex>\{a_i\}</tex> {{---}} множество некоторых объектов, занумерованных числами от одного до <tex>n</tex>. Тогда результатом действия перестановки на этот набор объектов назовём множество объектов <tex>\{b_i\}</tex>, занумерованных числами от одного до <tex>n</tex>, причём <tex>b_i = a_{\pi_i}</tex>.
+
Пусть <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>.
 
}}
 
}}
  
[[Файл:Permutation_action.png|400px|thumb|right|Иллюстрация действия перестановки]]
+
Обозначим за <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>, то [[Действие_группы_на_множестве|действие перестановки]] можно определить как композицию отображений <tex>\alpha \circ \pi</tex>.
  
Обозначим за <tex>A</tex> множество (не пронумерованных) объектов <tex>\{a_1, \dots, a_n\}</tex>. Поскольку перестановку можно рассматривать как отображение <tex>\pi \colon \{1, \dots, n\} \to \{1, \dots, n\}</tex>, а нумерацию как отображение <tex>\alpha \colon \{1, \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>. Если рассмотреть [[Основные_определения_теории_графов|граф]] перестановки (описано ниже), то действие перестановки можно представить таким образом: каждый элемент устанавливается в вершину графа, соответствующую номеру этого элемента, после чего каждый элемент передвигается по исходящему из этой вершины ребру.
  
Например, рассмотрим множество <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>\pi^n</tex> соответствует переходу по графу <tex>n</tex> раз.
  
Строка 25: Строка 26:
  
 
==Циклы==
 
==Циклы==
[[Файл:cycles.gif|150px|right|thumb|Изображение перестановки в виде графа]]
+
{{Определение
Циклом длины <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>. Перестановку можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: <tex>(1, 5, 2)(3, 6)(4)=\langle 5,1,6,4,2,3\rangle </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>.
Перестановку можно представить в виде графа. Граф содержит ребро от вершины <tex>x_i</tex> к вершине <tex>x_j</tex> если <tex>\pi(x_i) = x_j</tex>. Тогда циклы перестановки соответствуют циклическим путям в графе.
+
}}
 +
[[Файл:cycles.gif|150px|right|frame|Изображение перестановки в виде графа]]
 +
Перестановку можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: <tex>(1, 5, 2)(3, 6)(4)=\langle 5,1,6,4,2,3\rangle </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>. Тогда циклы перестановки соответствуют циклическим путям в графе.
  
 
С циклами связаны некоторые интересные свойства перестановок.
 
С циклами связаны некоторые интересные свойства перестановок.
 
{{Определение
 
{{Определение
|neat = 1
+
|definition='''Степенью перестановки''' называется минимальное число <tex>n \in N</tex> такое, что <tex>\pi^n = i</tex>}}
|definition=Степенью перестановки называется минимальное число <tex>n \in N</tex> такое, что <tex>\pi^n = i</tex>}}
 
 
 
 
 
 
 
 
 
  
 
{{Утверждение
 
{{Утверждение
Строка 45: Строка 45:
 
Степень перестановки равна наименьшему общему кратному длин всех циклов
 
Степень перестановки равна наименьшему общему кратному длин всех циклов
 
|proof=
 
|proof=
Пусть <tex>k</tex> - степень перестановки. Граф перестановки разбит на циклы, и для того, чтобы какой-то элемент прошёл по своему циклу один раз, нужно возвести перестановку в степень <tex>l</tex>, где <tex>l</tex> - длина цикла. Чтобы элемент прошёл цикл несколько раз и вернулся на своё место, перестановка должна быть возведена в степень кратную <tex>l</tex>. Тогда только в том случае, когда <tex>k</tex> делится на длины всех циклов, все элементы вернутся на свои места, а наименьшее такое <tex>k</tex> - это НОК длин всех циклов.  
+
Пусть <tex>k</tex> степень перестановки. Граф перестановки разбит на циклы, и для того, чтобы какой-то элемент прошёл по своему циклу один раз, нужно возвести перестановку в степень <tex>l</tex>, где <tex>l</tex> длина цикла. Если элемент проходит цикл несколько раз и возвращается на своё место, то можно сделать вывод о том, что перестановка возводится в степень кратную <tex>l</tex>. Тогда только в том случае, когда <tex>k</tex> делится на длины всех циклов, все элементы вернутся на свои места, а наименьшее такое <tex>k</tex> это НОК длин всех циклов. }}
}}
 
 
 
  
  
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
Если длины всех циклов не превышают 2, то перестановка является [[Умножение_перестановок,_обратная_перестановка,_группа_перестановок#def_involution | инволюцией]].
+
Если длины всех циклов не превышают <tex>2</tex>, то перестановка является [[Умножение_перестановок,_обратная_перестановка,_группа_перестановок#def_involution | инволюцией]].
 
|proof=
 
|proof=
Действительно, в таком случае по вышеупомянутому <tex>\pi^2 = i</tex>. Домножив на <tex>\pi^{-1}</tex> получим <tex>\pi^{-1} = \pi</tex>.  
+
Действительно, в таком случае по вышеупомянутому <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>''
 +
 
 +
==См. также==
 +
*[[Теорема Кэли]]
  
 
== Источники ==
 
== Источники ==
 
+
* [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 Википедия {{---}} Перестановка]
* [http://ru.wikipedia.org/wiki/%CF%E5%F0%E5%F1%F2%E0%ED%EE%E2%EA%E0 Википедия]
+
* [https://en.wikipedia.org/wiki/Permutation Wikipedia {{---}} Permutation]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]

Текущая версия на 21:19, 20 июня 2020

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

Определение:
Пусть [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                  // выведем на экран очередной цикл перестановки

См. также[править]

Источники[править]