Представить произведение циклов в виде перестановки

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

Обозначим за множество (не пронумерованных) объектов . Поскольку перестановку можно рассматривать как отображение , а нумерацию как отображение , то действие перестановки можно определить как композицию отображений .

Например, рассмотрим множество и перестановку . Тогда результат действия на – упорядоченное множество . Если рассмотреть граф перестановки (описано ниже), то действие перестановки можно представить таким образом: каждый элемент устанавливается в вершину графа, соответствующую номеру этого элемента, после чего каждый элемент передвигается по исходящему из этой вершины ребру.

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

Также, композицию перестановок можно выразить как действие одной перестановки на другую. Стоит отметить, что действие перестановки соответствует переходу по графу раз.

Действие обратной перестановки над множеством соответствует переходу элементов по развёрнутым рёбрам и даёт упорядоченное множество , для которого верно .

Циклы[править]

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

Перестановку можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: .

Цикл может быть записан по разному, например, в приведенном выше примере цикл может быть записан как , , но не может быть записан как .

Перестановку можно представить в виде графа. Граф содержит ребро от вершины к вершине если . Тогда циклы перестановки соответствуют циклическим путям в графе.

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

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

Рассмотрим элемент перестановки . Добавим его к циклу, отметим позицию посещенной и перейдем к . Если мы перешли в позицию , которую уже посещали, значит мы нашли очередной цикл перестановки. Перейдем к первой непосещенной позиции и продолжим поиск.

Рассмотрим в качестве примера поиск циклов в перестановке :

1. В позиции находится число . Добавим его к новому циклу и перейдем в позицию . Аналогично добавим к циклу числа и . Перейдем в позицию , которую мы уже посещали – нашли первый цикл .
2. Аналогично найдем второй цикл .
3. Таким образом,

Псевдокод алгоритма[править]

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] cycle // выведем на экран очередной цикл перестановки

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

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

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

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

Источник

Тип (математической) перестановки без фиксированного элемента

В математика , и, в частности, в теории групп , циклическая перестановка (или цикл ) – это перестановка элементы некоторого набора X, который отображает элементы некоторого подмножества S из X друг в друга циклическим образом, фиксируя (то есть, отображая на себя) все другие элементы X. Если S имеет k элементов, цикл называется k-циклом . Циклы часто обозначаются списком их элементов, заключенным в круглые скобки, в том порядке, в котором они переставлены.

Например, если X = {1, 2, 3, 4}, перестановка (1, 3, 2, 4), которая отправляет 1 в 3, 3 в 2, 2 в 4 и 4 в 1 (так что S = X) – это 4-цикл, и перестановка (1, 3, 2), которая отправляет 1 в 3, 3 в 2, 2 в 1 и 4 в 4 (поэтому S = {1, 2, 3} и 4 – фиксированный элемент) – это 3-цикл. С другой стороны, перестановка, которая отправляет 1 в 3, 3 в 1, 2 в 4 и 4 в 2, не является циклической перестановкой, потому что она отдельно переставляет пары {1, 3} и {2, 4}.

Набор S называется орбитой цикла. Любую перестановку на конечном числе элементов можно разложить на циклы на непересекающихся орбитах.

Циклическими частями перестановки являются циклы, таким образом, второй пример состоит из 3-цикла и 1-цикла (или фиксированной точки) и третий состоит из двух 2-циклов и обозначается (1, 3) (2, 4).

Определение

Схема циклической перестановки с двумя неподвижными точками; 6-цикл и два 1-цикла.

A перестановка называется циклической перестановкой тогда и только тогда, когда имеет единственный нетривиальный цикл (цикл длины>1).

Например, перестановка, записанная в двухстрочный (двумя способами), а также циклические обозначения,

(1 2 3 4 5 6 7 8 4 2 7 6 5 8 1 3 ) = (1 4 6 8 3 7 2 5 4 6 8 3 7 1 2 5) = (1 4 6 8 3 7) (2) (5), { displaystyle { begin {pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \ 4 & 2 & 7 & 6 & 5 & 8 & 1 & 3 end {pmatrix}} = { begin {pmatrix} 1 & 4 & 6 & 8 & 3 & 7 & 2 & 5 \ 4 & 6 & 8 & 3 & 7 & 1 & 2 & 5 end {pmatrix}} = (1 4 6 8 3 7) (2) (5),}

– шестерка -цикл; диаграмма его цикла показана справа.

Некоторые авторы ограничивают определение только теми перестановками, которые состоят из одного нетривиального цикла (то есть не допускаются фиксированные точки).

Циклическая перестановка без тривиальных циклов; 8-цикл.

Например, перестановка

(1 2 3 4 5 6 7 8 4 5 7 6 8 2 1 3) = (1 4 6 2 5 8 3 7 4 6 2 5 8 3 7 1) = (1 4 6 2 5 8 3 7) { displaystyle { begin {pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \ 4 & 5 & 7 & 6 & 8 & 2 & 1 & 3 end {pmatrix}} = { begin {pmatrix} 1 & 4 & 6 & 2 & 5 & 8 & 3 & 7 7 4 & 6} 7 4 & 6} = (1 4 6 2 5 8 3 7)}

является циклической перестановкой согласно этому более ограниченному определению, в то время как предыдущий пример – нет.

Более формально, перестановка σ { displaystyle sigma} множества X, рассматриваемая как биективная функция σ: X → X { displaystyle sigma: X to X} , называется циклом, если действие на X подгруппы, сгенерированной σ { displaystyle sigma} , имеет не более одной орбиты с более чем одним элементом. Это понятие чаще всего используется, когда X – конечное множество; тогда, конечно, самая большая орбита S также конечна. Пусть s 0 { displaystyle s_ {0}} будет любым элементом S, и положим si = σ i (s 0) { displaystyle s_ {i} = sigma ^ {i} (s_ {0})} для любого i ∈ Z { displaystyle i in mathbf {Z}} . Если S конечно, существует минимальное число k ≥ 1 { displaystyle k geq 1} , для которого sk = s 0 { displaystyle s_ {k} = s_ {0 }} . Тогда S = {s 0, s 1,…, sk – 1} { displaystyle S = {s_ {0}, s_ {1}, ldots, s_ {k-1} }} и σ { displaystyle sigma} – это перестановка, определяемая как

σ (si) = si + 1 { displaystyle sigma (s_ {i}) = s_ {i + 1}} для 0 ≤ i

и σ (x) = x { displaystyle sigma (x) = x} для любого элемента из Икс ∖ S { Displaystyle X setminus S} . Элементы, не зафиксированные в σ { displaystyle sigma} , можно представить как

s 0 ↦ s 1 ↦ s 2 ↦ ⋯ ↦ sk – 1 ↦ sk = s 0 { displaystyle s_ {0} mapsto s_ {1} mapsto s_ {2} mapsto cdots mapsto s_ {k-1} mapsto s_ {k} = s_ {0}} .

Цикл можно записать с помощью компактное обозначение цикла σ = (s 0 s 1… sk – 1) { displaystyle sigma = (s_ {0} ~ s_ {1} ~ dots ~ s_ {k-1}) )} (в этой нотации между элементами нет запятых, чтобы избежать путаницы с кортежем k- ). Длина цикла – это количество элементов его наибольшей орбиты. Цикл длины k также называется k-циклом.

Орбита 1-цикла называется фиксированной точкой перестановки, но в качестве перестановки каждый 1-цикл является тождественной перестановкой . Когда используется обозначение цикла, 1-циклы часто подавляются, когда не возникает путаницы.

Основные свойства

Одним из основных результатов для симметричных групп является то, что любые перестановку можно выразить как произведение непересекающихся циклов (точнее: циклов с непересекающимися орбитами); такие циклы коммутируют друг с другом, и выражение перестановки уникально с точностью до порядка циклов. мультимножество длин циклов в этом выражении (тип цикла ), следовательно, однозначно определяется перестановкой, и как сигнатура, так и класс сопряженности перестановка в симметричной группе определяется им.

Дано количество k-циклов в симметрической группе S n , для 1 ≤ k ≤ n { displaystyle 1 leq k leq n} , по следующим эквивалентным формулам

(nk) (k – 1)! знак равно N (N – 1) ⋯ (N – К + 1) К знак равно N! (п – к)! к { displaystyle { binom {n} {k}} (k-1)! = { frac {n (n-1) cdots (n-k + 1)} {k}} = { frac { n!} {(nk)! k}}}

k-цикл имеет сигнатуру (−1).

инверсия цикла σ = (s 0 s 1… sk – 1) { displaystyle sigma = (s_ {0} ~ s_ {1} ~ точки ~ s_ {k-1})} задается изменением порядка записей: σ – 1 = (sk – 1… s 1 s 0) { displaystyle sigma ^ { -1} = (s_ {k-1} ~ dots ~ s_ {1} ~ s_ {0})} . В частности, поскольку (a b) = (b a) { displaystyle (a ~ b) = (b ~ a)} , каждый два цикла является своим собственным обратным. Поскольку непересекающиеся циклы коммутируют, обращение к произведению непересекающихся циклов является результатом обращения каждого из циклов отдельно.

Транспозиции

Цикл только с двумя элементами называется транспонированием . Например, перестановка π = (1 2 3 4 1 4 3 2) { displaystyle pi = { begin {pmatrix} 1 & 2 & 3 & 4 \ 1 & 4 & 3 & 2 end {pmatrix}}} , что местами 2 и 4.

Свойства

Любая перестановка может быть выражена как композиция (продукт) транспозиций – формально они являются генераторами для группа . Фактически, когда переставляемый набор равен {1, 2, …, n} для некоторого целого числа n, тогда любая перестановка может быть выражена как произведение смежных транспозиций (1 2) , (2 3), (3 4), { displaystyle (1 ~ 2), (2 ~ 3), (3 ~ 4),} и так далее. Это следует потому, что произвольное транспонирование может быть выражено как произведение смежных транспозиций. Конкретно, можно выразить транспозицию (kl) { displaystyle (k ~~ l)} , где k , перемещая k на l по одному шагу за раз, а затем перемещая l обратно туда, где k was, который меняет местами эти два и не вносит никаких других изменений:

(kl) = (kk + 1) ⋅ (k + 1 k + 2) ⋯ (l – 1 l) ⋅ (l – 2 l – 1) ⋯ (кк + 1). { Displaystyle (к ~~ l) = (к ~~ k + 1) cdot (k + 1 ~~ k + 2) cdots (l-1 ~~ l) cdot (l-2 ~~ l- 1) cdots (k ~~ k + 1).}

Разложение перестановки в продукт транспозиций получается, например, записывая перестановку как произведение непересекающихся циклов, а затем итеративно разбивая каждый из циклов длины 3 и более в произведение транспозиции и цикла длины на единицу меньше:

(abcd… yz) = (ab) ⋅ (bcd… yz). { displaystyle (a ~ b ~ c ~ d ~ ldots ~ y ~ z) = (a ~ b) cdot (b ~ c ~ d ~ ldots ~ y ~ z).}

Это означает начальный запрос заключается в перемещении a { displaystyle a} в b, { displaystyle b,} b { displaystyle b} в с, { displaystyle c,} y { displaystyle y} до z, { displaystyle z,} и, наконец, z { displaystyle z} – a. { displaystyle a.} Вместо этого можно свернуть элементы, сохраняя a { displaystyle a} там, где он находится, выполнив сначала правильный коэффициент (как обычно в обозначении операторов, и следуя соглашению из статьи о перестановках ). Это переместило z { displaystyle z} в позицию b, { displaystyle b,} , поэтому после первой перестановки элементы a { displaystyle a} и z { displaystyle z} еще не на своих конечных позициях. После этого выполняется транспонирование (ab), { displaystyle (a ~ b),} , затем адрес z { displaystyle z} по индексу b { displaystyle b} , чтобы поменять местами то, что изначально было a { displaystyle a} и z. { displaystyle z.}

Фактически, симметрическая группа является группой Кокстера , что означает, что она генерируется элементами порядка 2 (смежные транспозиции), и все отношения имеют определенную форму.

Один из основных результатов о симметричных группах утверждает, что либо все разложения данной перестановки на транспозиции имеют четное количество транспозиций, либо все они имеют нечетное количество транспозиций. Это позволяет четности перестановки быть четко определенной концепцией .

См. Также

• Циклическая сортировка – алгоритм сортировки, основанный на идее, что сортируемая перестановка может быть разложена на циклы, которые можно по отдельности чередовать для получения отсортированного результата
• Циклы и фиксированные точки
• Циклическая перестановка целого числа
• Обозначение цикла
• Циклическая перестановка в белках

Примечания

Ссылки

Источники

• Андерсон, Марлоу и Фейл , Тодд (2005), Первый курс абстрактной алгебры, Chapman & Hall / CRC; 2-е издание. ISBN1-58488-515-7 .
• Фрали, Джон (1993), Первый курс абстрактной алгебры (5-е изд.), Эддисон Уэсли, ISBN 978-0-201-53467-2
• Ротман, Джозеф Дж. (2006), Первый курс абстрактной алгебры с приложениями (3-е изд.), Прентис-Холл, ISBN 978-0-13-186267-8
• Саган, Брюс Э. (1991), Симметричная группа / представления, комбинаторные алгоритмы и симметричные функции, Wadsworth & Brooks / Cole, ISBN 978-0-534-15540-7

Внешние ссылки

Эта статья включает материал из цикла по PlanetMath , который находится под лицензией Creative Commons Attribution / Совместная лицензия .

Источник

6 перестановок трёх шаров

Перестано́вка в комбинаторике – упорядоченный набор без повторений чисел обычно трактуемый как биекция на множестве , которая числу ставит в соответствие -й элемент из набора. Число при этом называется длиной перестановки[1].

В теории групп под перестановкой произвольного множества подразумевается биекция этого множества на себя. Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют наглядный способ записи перестановки. Более существенное отличие состоит в том, что подстановка – это непосредственно функция, а перестановка – результат применения этой функции к элементам последовательности.)

Термин «перестановка» возник потому, что сначала брались объекты, каким-то образом расставленные, а другие способы упорядочения требовали переставить эти объекты.[2].

Свойства[править | править код]

Число всех перестановок из элементов равно числу размещений из по , то есть факториалу[3][4][5][6]:

.

Композиция определяет операцию произведения на перестановках одной длины: Относительно этой операции множество перестановок из элементов образует группу, которую называют симметрической и обычно обозначают .

Любая конечная группа из элементов изоморфна некоторой подгруппе симметрической группы (теорема Кэли). При этом каждый элемент сопоставляется с перестановкой , задаваемой на элементах тождеством где – групповая операция в .

Связанные определения[править | править код]

Носитель перестановки – это подмножество множества , определяемое как

Неподвижной точкой перестановки является всякая неподвижная точка отображения , то есть элемент множества Множество всех неподвижных точек перестановки является дополнением её носителя в .

Инверсией в перестановке называется всякая пара индексов такая, что и . Чётность числа инверсий в перестановке определяет чётность перестановки.

Специальные типы перестановок[править | править код]

Подстановка[править | править код]

Перестановка множества может быть записана в виде подстановки, например:

где и .

Произведения циклов и знак перестановки[править | править код]

Любая перестановка может быть разложена в произведение (композицию) непересекающихся циклов длины , причём единственным образом с точностью до порядка следования циклов в произведении. Например:

Часто также считают, что неподвижные точки перестановки представляют собой самостоятельные циклы длины 1, и дополняют ими цикловое разложение перестановки. Для приведенного выше примера таким дополненным разложением будет . Количество циклов разной длины, а именно набор чисел , где – это количество циклов длины , определяет цикловую структуру перестановки. При этом величина равна длине перестановки, а величина равна общему количеству циклов. Количество перестановок из элементов с циклами даётся числом Стирлинга первого рода без знака .

Любой цикл может быть разложен в произведение (не обязательно непересекающихся) транспозиций. При этом цикл длины 1 (являющийся по сути тождественной перестановкой ) можно представить как пустое произведение (англ.) транспозиций или, например, как квадрат любой транспозиции: Цикл длины можно разложить в произведение транспозиций следующим образом:

Следует заметить, что разложение циклов на произведение транспозиций не является единственным:

Таким образом, любая перестановка может быть разложена в произведение транспозиций. Хотя это можно сделать многими способами, чётность количества транспозиций во всех таких разложениях одинакова. Это позволяет определить знак перестановки (чётностью перестановки или сигнатурой перестановки) как:

где – количество транспозиций в каком-то разложении . При этом называют чётной перестановкой, если , и нечётной перестановкой, если .

Эквивалентно, знак перестановки определяется её цикловой структурой: знак перестановки из элементов, состоящий из циклов, равен

.

Знак перестановки также может быть определён через количество инверсий в :

.

Перестановки с повторением[править | править код]

Рассмотрим элементов различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если – количество элементов -го типа, то и количество всевозможных перестановок с повторениями равно мультиномиальному коэффициенту

Перестановку с повторениями можно также рассматривать как перестановку мультимножества мощности .

Случайная перестановка[править | править код]

Случайной перестановкой называется случайный вектор все элементы которого принимают натуральные значения от 1 до и при этом вероятность совпадения любых двух элементов равна 0.

Независимой случайной перестановкой называется такая случайная перестановка , для которой:

для некоторых таких, что:

Если при этом не зависят от , то перестановку называют одинаково распределённой. Если же нет зависимости от , то есть то называют однородной.

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

• Гигантская компонента
• Сочетание
• Размещение
• Анаграмма
• Симметрическая группа
• Алгоритм Нарайаны

Примечания[править | править код]

Литература[править | править код]

• Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and ing. – 2-е изд. – М.: «Вильямс», 2007. – С. 824. – ISBN 0-201-89685-0.
• Кострикин А. И. Введение в алгебру. Основы алгебры. – М.: Физматлит, 1994. – С. 59-71. – 320 с. – ISBN 5-02-014644-7.
• Сергей Мельников. Перестановки, сочетания, размещения: вывод всех перестановок // Delphi и Turbo Pascal на занимательных примерах. – БХВ-Петербург, 2012. – 448 с. – ISBN 978-5-94157-886-3.

Ссылки[править | править код]

• Аранжеман // Энциклопедический словарь Брокгауза и Ефрона : в 86 т. (82 т. и 4 доп.). – СПб., 1890-1907.

Источник