Перестановка

Каждая из шести строк представляет собой перестановку трех разных шаров.

В математике , А перестановка из множества есть, грубо говоря, расположение ее членов в последовательность или линейный порядок , или если множество уже заказало, перегруппировка ее элементы. Слово «перестановка» также относится к действию или процессу изменения линейного порядка упорядоченного набора. ^[1]

Перестановки отличаются от комбинаций , которые представляют собой выбор некоторых членов набора независимо от порядка. Например, записанное в виде кортежей , существует шесть перестановок набора {1,2,3}, а именно: (1,2,3), (1,3,2), (2,1,3), (2 , 3,1), (3,1,2) и (3,2,1). Это все возможные порядки этого трехэлементного набора. Анаграммы слов, буквы которых отличаются друг от друга, также являются перестановками: буквы уже упорядочены в исходном слове, а анаграмма - это перестановка букв. Изучение перестановок конечных множеств - важная тема в области комбинаторики и теории групп .

Перестановки используются почти во всех областях математики и во многих других областях науки. В информатике они используются для анализа алгоритмов сортировки ; в квантовой физике для описания состояний частиц; и в биологии для описания последовательностей РНК .

Количество перестановок n различных объектов равно n  факториалу , обычно записываемому как n ! , что означает произведение всех положительных целых чисел, меньших или равных n .

Технически, перестановка множества S определяется как биекции от S к самому себе. ^{[2] [3]} То есть это функция от S до S, для которой каждый элемент встречается ровно один раз как значение изображения . Это связано с перестановкой элементов S, в которой каждый элемент s заменяется соответствующим f ( s ) . Например, указанная выше перестановка (3,1,2) описывается функцией, определенной как:${\ displaystyle \ alpha}$

${\ Displaystyle \ альфа (1) = 3, \ четырехъядерный \ альфа (2) = 1, \ четырехъядерный \ альфа (3) = 2}$.

Совокупность всех перестановок набора образует группу, называемую симметрической группой набора. Групповая операция - это композиция (последовательное выполнение двух заданных перестановок), которая приводит к другой перегруппировке. Поскольку свойства перестановок не зависят от природы элементов набора, часто при изучении перестановок учитываются именно перестановки набора . ${\ Displaystyle \ {1,2, \ ldots, п \}}$

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

В популярной головоломке « Кубик Рубика», изобретенной в 1974 году Эрно Рубиком , каждый поворот граней головоломки создает перестановку цветов поверхности.

История [ править ]

Перестановки, называемые гексаграммами, использовались в Китае в И Цзин ( Пиньинь : И Цзин) еще в 1000 году до нашей эры.

Аль-Халил (717–786), арабский математик и криптограф , написал Книгу криптографических сообщений . Он содержит первое использование перестановок и комбинаций , чтобы перечислить все возможные арабские слова с гласными и без них. ^[4]

Правило определения количества перестановок n объектов было известно в индийской культуре около 1150 года. В « Лилавати » индийского математика Бхаскары II содержится отрывок, который переводится как:

Произведением умножения начала и увеличения арифметического ряда на единицу и продолженного до количества знаков будут вариации числа с конкретными цифрами. ^[5]

В 1677 году Фабиан Стедман описал факториалы при объяснении количества перестановок колоколов в переменном звоне . Начиная с двух колокольчиков: «во-первых, два должны быть допущены для изменения двумя способами», что он иллюстрирует, показывая 1 2 и 2 1. ^[6] Затем он объясняет, что с тремя колокольчиками «трижды две цифры должны быть произведено из трех », что еще раз проиллюстрировано. Его объяснение включает в себя «отбросьте 3, и 1.2 останется; отбросьте 2, и 1.3 останется; отбросьте 1, и 2.3 останется». ^[7] Затем он переходит к четырем колокольчикам и повторяет аргумент отвержения, показывающий, что будет четыре разных набора из трех. По сути, это рекурсивный процесс. Он продолжает с пятью колокольчиками, используя метод «отбрасывания», и составляет итоговые 120 комбинаций. ^{[8] Здесь} он сдается и замечает:

Природа этих методов такова, что изменения одного числа включают изменения всех меньших чисел ... до такой степени, что кажется, что полный Звук изменений одного числа формируется путем объединения завершенных Звонков на всех меньших числах. в одно целое тело; ^[9]

Стедман расширяет рассмотрение перестановок; он продолжает рассматривать количество перестановок букв алфавита и лошадей из конюшни 20. ^[10]

Первый случай, когда кажущиеся несвязанными математические вопросы изучались с помощью перестановок, произошел примерно в 1770 году, когда Жозеф Луи Лагранж , изучая полиномиальные уравнения, заметил, что свойства перестановок корней уравнения связаны с возможностями Найди решение. Это направление работы в конечном итоге привело к работе Эвариста Галуа в теории Галуа , которая дает полное описание того, что возможно и что невозможно в отношении решения полиномиальных уравнений (с одним неизвестным) с помощью радикалов. В современной математике существует множество подобных ситуаций, в которых понимание проблемы требует изучения определенных перестановок, связанных с ней.

Перестановки без повторов [ править ]

Простейший пример перестановок - перестановки без повторов, где мы рассматриваем количество возможных способов размещения n элементов в n местах. Факторный имеет особое применение в определении числа перестановок в наборе , который не включает в себя повторы. Число n !, читаемое «n факториал», ^[11] - это как раз то количество способов, которыми мы можем переставить n вещей в новый порядок. Например, если у нас есть три фрукта: апельсин, яблоко и груша, мы можем съесть их в указанном порядке или изменить их (например, яблоко, груша, затем апельсин). Тогда точное количество перестановок . Число становится чрезвычайно большим по мере увеличения количества элементов (n).${\ Displaystyle 3! = 1 \ cdot 2 \ cdot 3 = 6}$

Аналогичным образом, количество комбинаций r элементов из n объектов считается частичной перестановкой. Оно записывается как (читается как «n переставить г») и равно числу (также записанному как ). ^{[12] [13] [14]}${\ displaystyle nPr}$${\ Displaystyle п (п-1) \ cdots (п-г + 1)}$${\ displaystyle n! / (nr)!}$

Определение [ править ]

В математических текстах принято обозначать перестановки строчными греческими буквами. Обычно используются либо и , либо и . ^[15]${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ displaystyle \ sigma, \ tau}$${\ displaystyle \ pi}$

Подстановки можно определить как биекции из множества S в себя. Все перестановки набора с n элементами образуют симметричную группу , обозначенную , где групповая операция - композиция функций . Таким образом, для двух перестановок и в группе выполняются четыре групповые аксиомы: ${\ displaystyle S_ {n}}$${\ displaystyle \ pi}$${\ displaystyle \ sigma}$${\ displaystyle S_ {n}}$

1. Закрытие : если и есть, значит, так и есть${\ displaystyle \ pi}$${\ displaystyle \ sigma}$${\ displaystyle S_ {n}}$${\ displaystyle \ pi \ sigma.}$
2. Ассоциативность : Для любых трех перестановок ,${\ Displaystyle \ пи, \ сигма, \ тау \ в S_ {п}}$${\ Displaystyle (\ пи \ сигма) \ тау = \ пи (\ сигма \ тау).}$
3. Идентичность : существует перестановка идентичности, обозначаемая и определяемая для всех . Для любого ,${\ displaystyle \ operatorname {id}}$${\ displaystyle \ operatorname {id} (x) = x}$${\ displaystyle x \ in S}$${\ Displaystyle \ sigma \ в S_ {п}}$${\ displaystyle \ operatorname {id} \ sigma = \ sigma \ operatorname {id} = \ sigma.}$
4. Обратимость : для каждой перестановки существует так, что${\ displaystyle \ pi \ in S_ {n}}$${\ displaystyle \ pi ^ {- 1} \ in S_ {n}}$${\ displaystyle \ pi \ pi ^ {- 1} = \ pi ^ {- 1} \ pi = \ operatorname {id}.}$

В общем случае композиция двух перестановок не коммутативна , т. Е.${\ displaystyle \ pi \ sigma \ neq \ sigma \ pi.}$

Как биекция набора самому себе, перестановка - это функция, которая выполняет перегруппировку набора, а не сама перегруппировка. Более старая и более элементарная точка зрения состоит в том, что перестановки - это сами перестановки. Чтобы различать эти два идентификатора, активные и пассивные идентификаторы иногда добавляются к термину перестановка , тогда как в старой терминологии используются подстановки и перестановки . ^[16]

Перестановка может быть разложена на один или несколько непересекающихся циклов , то есть орбиты , которые находятся путем многократного отслеживания применения перестановки к некоторым элементам. Например, перестановка, определяемая с помощью, имеет 1-цикл, в то время как перестановка, определенная с помощью и, имеет 2-цикл (подробности о синтаксисе см. В § Обозначение цикла ниже). В общем случае цикл длины k , то есть состоящий из k элементов, называется k -циклом.${\ displaystyle \ sigma}$${\ Displaystyle \ sigma (7) = 7}$${\ Displaystyle (\, 7 \,)}$${\ displaystyle \ pi}$${\ Displaystyle \ pi (2) = 3}$${\ Displaystyle \ pi (3) = 2}$${\ Displaystyle (\, 2 \, 3 \,)}$

Элемент в 1-цикле называется фиксированной точкой перестановки. Перестановка без неподвижных точек называется расстройством . 2-циклы называются транспозициями ; такие перестановки просто меняют два элемента, оставляя остальные неизменными.${\ Displaystyle (\, х \,)}$

Обозначения [ править ]

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

Двухстрочная запись [ править ]

В Коши «с двумя линиями обозначений , ^[17] один перечисляет элементы S в первом ряду, и для каждого из них его образ под ним во втором ряду. Например, конкретная перестановка множества S = {1,2,3,4,5} может быть записана как:

${\ displaystyle \ sigma = {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1 \ end {pmatrix}};}$

это означает, что σ удовлетворяет σ (1) = 2 , σ (2) = 5 , σ (3) = 4 , σ (4) = 3 и σ (5) = 1 . Элементы S могут появляться в любом порядке в первой строке. Эту перестановку можно также записать как:

${\ displaystyle \ sigma = {\ begin {pmatrix} 3 & 2 & 5 & 1 & 4 \\ 4 & 5 & 1 & 2 & 3 \ end {pmatrix}},}$

или же

${\ displaystyle \ sigma = {\ begin {pmatrix} 5 & 1 & 4 & 3 & 2 \\ 1 & 2 & 3 & 4 & 5 \ end {pmatrix}}.}$

Однострочные обозначения [ править ]

Если существует «естественный» порядок элементов S , скажем ^[a] , то его используют для первой строки двухстрочной записи:${\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n}}$

${\ displaystyle \ sigma = {\ begin {pmatrix} x_ {1} & x_ {2} & x_ {3} & \ cdots & x_ {n} \\\ sigma (x_ {1}) & \ sigma (x_ {2}) & \ sigma (x_ {3}) & \ cdots & \ sigma (x_ {n}) \ end {pmatrix}}.}$

В этом предположении можно опустить первую строку и записать перестановку в однострочном обозначении как

${\ Displaystyle (\ sigma (x_ {1}) \; \ sigma (x_ {2}) \; \ sigma (x_ {3}) \; \ cdots \; \ sigma (x_ {n}))}$,

то есть упорядоченное расположение S. ^{[18] [19]} Следует проявлять осторожность, чтобы отличать однострочное обозначение от обозначения цикла, описанного ниже. В математической литературе принято опускать круглые скобки для однострочных обозначений и использовать их для обозначений циклов. Однострочное обозначение также называется словесным представлением перестановки. ^[20] В приведенном выше примере будет 2 5 4 3 1, поскольку для первой строки предполагается естественный порядок 1 2 3 4 5. (Обычно эти записи разделяются запятыми только в том случае, если некоторые из них состоят из двух или более цифр.) Эта форма более компактна и распространена в элементарной комбинаторике и информатике.. Это особенно полезно в приложениях, где элементы S или перестановки должны сравниваться как больше или меньше.

Обозначение цикла [ править ]

Обозначение цикла описывает эффект многократного применения перестановки к элементам набора. Он выражает перестановку как продукт циклов ; поскольку различные циклы не пересекаются , это называется «разложением на непересекающиеся циклы». ^[b]

Чтобы записать перестановку в обозначении цикла, поступают следующим образом:${\ displaystyle \ sigma}$

1. Напишите открывающую скобку, затем выберите произвольный элемент x из и запишите его:${\ displaystyle S}$${\ Displaystyle (\, х}$
2. Затем проследите орбиту x ; то есть запишите его значения при последовательном применении :${\ displaystyle \ sigma}$${\ Displaystyle (\, х \, \ сигма (х) \, \ сигма (\ сигма (х)) \, \ ldots}$
3. Повторяйте, пока значение не вернется к x, и запишите закрывающую скобку вместо x :${\ Displaystyle (\, х \, \ сигма (х) \, \ сигма (\ сигма (х)) \, \ ldots \,)}$
4. Теперь перейдите к элементу y из S , который еще не записан, и действуйте таким же образом:${\ Displaystyle (\, х \, \ сигма (х) \, \ сигма (\ сигма (х)) \, \ ldots \,) (\, у \, \ ldots \,)}$
5. Повторяйте, пока все элементы S не будут записаны циклами.

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

${\ Displaystyle {\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1 \ end {pmatrix}} = (\, 1 \, 2 \, 5 \,) (\, 3 \, 4 \,) = (\, 3 \, 4 \,) (\, 1 \, 2 \, 5 \,) = (\, 3 \, 4 \,) (\, 5 \, 1 \, 2 \,).}$

1-циклы часто опускаются из обозначения цикла, если контекст понятен; для любого элемента x в S, не появляющегося ни в каком цикле, неявно предполагается . ^[21] тождественная перестановка , которая состоит только из 1-циклов, может быть обозначена с помощью одного 1-цикла (х), по числу 1, ^[C] или с помощью идентификатора . ^{[22] [23]}${\ Displaystyle \ sigma (х) = х}$

Удобная особенность обозначения цикла состоит в том, что можно найти инверсию перестановки, просто изменив порядок элементов в циклах перестановки. Например

${\ Displaystyle [(\, 1 \, 2 \, 5 \,) (\, 3 \, 4 \,)] ^ {- 1} = (\, 5 \, 2 \, 1 \,) (\, 4 \, 3 \,)}$

Обозначение канонического цикла (также известное как стандартная форма) [ править ]

В некоторых комбинаторных контекстах полезно зафиксировать определенный порядок элементов в циклах и самих (непересекающихся) циклов. Миклош Бона называет следующие варианты упорядочения нотацией канонического цикла :

• в каждом цикле самый большой элемент указывается первым
• циклы сортируются в порядке возрастания их первого элемента

Например, (312) (54) (8) (976) - это перестановка в канонической записи цикла. ^[24] Каноническая запись цикла не пропускает одноцикловых.

Ричард П. Стэнли называет такой же выбор представления «стандартным представлением» перестановки. ^[25] и Мартин Айгнер использует термин «стандартная форма» для обозначения того же понятия. ^[20] Сергей Китаев также использует терминологию «стандартной формы», но меняет оба варианта; то есть каждый цикл сначала перечисляет свой наименьший элемент, а циклы сортируются в порядке убывания их наименьшего элемента, то есть первых элементов. ^[26]

Состав перестановок [ править ]

Есть два способа обозначить композицию двух перестановок. - функция, которая отображает любой элемент x набора в . Самая правая перестановка применяется к аргументу первой ^[27] из-за способа написания приложения функции. ${\ displaystyle \ sigma \ cdot \ pi}$${\ Displaystyle \ сигма (\ пи (х))}$

Так как композиция функций является ассоциативной , поэтому является операция композиции на перестановках: . Следовательно, произведения более двух перестановок обычно пишутся без добавления скобок для выражения группировки; они также обычно пишутся без точки или другого знака для обозначения композиции.${\ Displaystyle (\ сигма \ пи) \ тау = \ сигма (\ пи \ тау)}$

Некоторые авторы предпочитают, чтобы первым действовал крайний левый фактор, ^{[28] [29] [30],} но для этого перестановки должны быть записаны справа от их аргумента, часто в виде экспоненты, где σ, действующий на x , записывается как x ^σ ; тогда произведение определяется как x ^{σ · π} = ( x ^σ ) ^π . Однако это дает другое правило для умножения перестановок; в этой статье используется определение, в котором сначала применяется самая правая перестановка.

Другие варианты использования термина « перестановка» [ править ]

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

k -перестановки n [ править ]

Более слабое значение термина « перестановка» , которое иногда используется в текстах по элементарной комбинаторике, обозначает те упорядоченные расположения, в которых ни один элемент не встречается более одного раза, но без требования использования всех элементов из данного набора. Это не перестановки, за исключением особых случаев, а естественные обобщения концепции упорядоченного расположения. Действительно, это использование часто включает рассмотрение компоновок фиксированной длины  k элементов, взятых из данного набора размера n , другими словами, эти k -перестановки n представляют собой различные упорядоченные компоновки k -элементного подмножества n -множества (иногда называемые вариациями илиаранжировки в более старой литературе ^[d] ). Эти объекты также известны как частичные перестановки или последовательности без повторов , термины, которые избегают путаницы с другим, более распространенным значением слова «перестановка». Число таких -permutations из обозначается по- разному такими символами , как , , , , или , и его значение определяется произведением ^[31]${\ displaystyle k}$${\ displaystyle n}$${\ Displaystyle P_ {k} ^ {n}}$${\ displaystyle _ {n} P_ {k}}$${\ displaystyle ^ {n} P_ {k}}$${\ displaystyle P_ {n, k}}$${\ Displaystyle P (п, к)}$

${\displaystyle P(n,k)=\underbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} _{k\ \mathrm {factors} }}$,

который равен 0, когда k > n , и в противном случае равен

${\displaystyle {\frac {n!}{(n-k)!}}.}$

Продукт хорошо определен без предположения, что он является неотрицательным целым числом, а также имеет значение вне комбинаторики; он известен как символ Похгаммера или в качестве -го падения факторной мощности из .${\displaystyle n}$ ${\displaystyle (n)_{k}}$${\displaystyle k}$${\displaystyle n^{\underline {k}}}$${\displaystyle n}$

Такое использование термина « перестановка» тесно связано с термином « комбинация» . К -элементное сочетание п -set S является K элементом подмножество S , элементы которого не упорядочены. Принимая все к элементным подмножествам S и заказным каждому из них всех возможных способов, мы получаем все K -permutations из S . Количество k- комбинаций n -множества C ( n , k ), следовательно, связано с количеством k-перестановки n на:

${\displaystyle C(n,k)={\frac {P(n,k)}{P(k,k)}}={\frac {\tfrac {n!}{(n-k)!}}{\tfrac {k!}{0!}}}={\frac {n!}{(n-k)!\,k!}}.}$

Эти числа также известны как биномиальные коэффициенты и обозначаются .${\displaystyle {\binom {n}{k}}}$

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

Упорядоченные расположения n элементов набора S , где разрешено повторение, называются n -наборами . Иногда их называют перестановками с повторением , хотя в целом они не являются перестановками. В некоторых контекстах они также называются словами в алфавите S. Если множество S имеет K элементов, число п -наборов над S является Там нет ограничений на том , как часто элемент может появляться в п -кратного, но если ограничения накладываются на том , как часто может появиться элемент, эта формула более не действительно.${\displaystyle k^{n}.}$

Перестановки мультимножеств [ править ]

Если М является конечным мультимножеством , то мультимножеством перестановка является упорядоченное расположение элементов М , в которой каждый элемент появляется число раз , равное точности его кратность в М . Анаграмма слова , имеющего несколько повторяющихся букв является примером мультинабора перестановки. ^[е] Если кратности элементов М (принятые в некотором порядке) являются , , ..., и их сумма (то есть, размер М ) является п , то число мультимножеств перестановок M задается мультиномиальный коэффициент ,${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle m_{l}}$^[32]

${\displaystyle {n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}={\frac {\left(\sum _{i=1}^{l}{m_{i}}\right)!}{\prod _{i=1}^{l}{m_{i}!}}}.}$

Например, количество различных анаграмм слова MISSISSIPPI составляет: ^[33]

${\displaystyle {\frac {11!}{1!\,4!\,4!\,2!}}=34650}$.

К-перестановки из мультинабора М представляет собой последовательность длину к элементам М , в которой каждый элемент появляется несколько раз меньше , чем или равно его кратности в М (элемент в числе повторений ).

Круговые перестановки [ править ]

Перестановки, когда их рассматривают как расположения, иногда называют линейно упорядоченными расположениями. В этих механизмах есть первый элемент, второй элемент и так далее. Если, однако, объекты расположены по кругу, этот выделенный порядок больше не существует, то есть в расположении нет «первого элемента», любой элемент можно рассматривать как начало расположения. Расположение объектов по кругу называется круговой перестановкой . ^{[34] [f]} Их можно формально определить как классы эквивалентности обычных перестановок объектов для отношения эквивалентности, порожденного перемещением последнего элемента линейного устройства на передний план.

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

 1 4 4 3 2 1 2 3

Круговое расположение следует читать против часовой стрелки, поэтому следующие два не эквивалентны, поскольку никакое вращение не может привести друг к другу.

 1 1 4 3 3 4 2 2

Число круговых перестановок множества S с n элементами равно ( n  - 1) !.

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

Количество перестановок n различных объектов равно n !.

Число n -перестановок с k непересекающимися циклами - это беззнаковое число Стирлинга первого рода , обозначаемое c ( n , k ) . ^[35]

Тип перестановки [ править ]

Циклы разбиения перестановок Множество так длин циклов перестановки образуют перегородку из п называется тип цикла из . В типе цикла есть «1» для каждой фиксированной точки σ, «2» для каждой транспозиции и так далее. Тип цикла - (3,2,2,1), который иногда записывается в более компактной форме как [1 ¹ 2 ² 3 ¹ ]. ${\displaystyle S_{n}}$${\displaystyle \sigma }$${\displaystyle \sigma }$${\displaystyle \beta =(\,1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)}$

Общий вид:, где - количество циклов соответствующей длины. Количество перестановок определенного типа ^[36]${\displaystyle [1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}]}$${\displaystyle \alpha _{1},\ldots ,\alpha _{n}}$

${\displaystyle {\frac {n!}{1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}\alpha _{1}!\alpha _{2}!\dotsm \alpha _{n}!}}}$.

Сопряжение перестановок [ править ]

В общем, составление перестановок, записанных в нотации цикла, не следует легко описываемому образцу - циклы композиции могут отличаться от составляемых. Однако структура цикла сохраняется в частном случае сопряжения перестановки другой перестановкой , что означает формирование продукта . Здесь, является сопряженным из и его цикла обозначение можно получить, взяв обозначение цикла для и применения ко всем записям в ней. ^[37] Отсюда следует, что две перестановки сопряжены именно тогда, когда они имеют один и тот же тип.${\displaystyle \sigma }$${\displaystyle \pi }$${\displaystyle \pi \sigma \pi ^{-1}}$${\displaystyle \pi \sigma \pi ^{-1}}$${\displaystyle \sigma }$${\displaystyle \sigma }$${\displaystyle \pi }$

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

Порядок перестановки - наименьшее положительное целое число m, чтобы . Это наименьшее общее кратное длины его цикла. Например, порядок является .${\displaystyle \sigma }$${\displaystyle \sigma ^{m}=\mathrm {id} }$${\displaystyle (\,1\,3\,2)(\,4\,5\,)}$${\displaystyle 2\cdot 3=6}$

Четность перестановки [ править ]

Каждую перестановку конечного множества можно выразить как произведение транспозиций. ^[38] Хотя может существовать много таких выражений для данной перестановки, все они содержат четное или нечетное количество транспозиций. Таким образом, все перестановки можно классифицировать как четные или нечетные в зависимости от этого числа.

Этот результат можно расширить , присвоив каждой перестановке знак , записанный . если - четное, а если - нечетное. Тогда для двух перестановок и${\displaystyle \operatorname {sgn} \sigma }$${\displaystyle \operatorname {sgn} \sigma =+1}$${\displaystyle \sigma }$${\displaystyle \operatorname {sgn} \sigma =-1}$${\displaystyle \sigma }$${\displaystyle \sigma }$${\displaystyle \pi }$

${\displaystyle \operatorname {sgn} (\sigma \pi )=\operatorname {sgn} \sigma \cdot \operatorname {sgn} \pi .}$

Следует, что ${\displaystyle \operatorname {sgn} \left(\sigma \sigma ^{-1}\right)=+1.}$

Матричное представление [ править ]

Можно представить перестановку {1, 2, ..., n } в виде матрицы размера n × n . Есть два естественных способа сделать это, но только один, для которого умножение матриц соответствует умножению перестановок в том же порядке: это тот, который связывает с σ матрицу M , элемент M _{i , j которой} равен 1, если i = σ ( j ) и 0 в противном случае. Результирующая матрица имеет ровно одну запись 1 в каждом столбце и в каждой строке и называется матрицей перестановок . Вот список этих матриц для перестановок 4 элементов. В
Таблица Кэли справа показывает эти матрицы для перестановок из 3 элементов.

Лемма Фоата о переходе [ править ]

Между однострочным и каноническим циклическим обозначением существует взаимосвязь. Рассмотрим перестановку в канонической нотации цикла, если мы удалим ее круглые скобки, мы получим перестановку в однострочной нотации. Лемма Фоата о переходе устанавливает природу этого соответствия как биекции на множестве n -перестановок (на себя). ^[39] Ричард П. Стэнли называет это соответствие фундаментальной биекцией . ^[25]${\displaystyle (\,2\,)(\,3\,1\,)}$${\displaystyle (2,3,1)}$

Позвольте быть преобразованием, стирающим скобки. Обратное к немного менее интуитивно понятно. Начиная с однострочной записи , первый цикл в канонической записи цикла должен начинаться с . Пока следующие элементы меньше чем , мы находимся в том же цикле. Второй цикл начинается с наименьшего индекса, такого что . Другими словами, он больше, чем все остальное слева от него, поэтому он называется максимумом слева направо . Каждый цикл в канонической нотации цикла начинается с максимума слева направо. ^[39]${\displaystyle f}$${\displaystyle q=f(p)}$${\displaystyle q=q_{1}q_{2}\cdots q_{n}}$${\displaystyle q_{1}}$${\displaystyle q_{1}}$${\displaystyle j}$${\displaystyle q_{j}>q_{1}}$${\displaystyle q_{j}}$

Например, в однострочном обозначении 5 - это первый элемент, больший 3, поэтому должен быть первый цикл . Тогда 8 - следующий элемент больше 5, значит, второй цикл . Поскольку 9 больше 8, это сам по себе цикл. Наконец, 9 больше, чем все остальные элементы справа, поэтому последний цикл больше .${\displaystyle (3,1,2,5,4,8,9,7,6)}$${\displaystyle (\,3\,1\,2\,)}$${\displaystyle (\,5\,4\,)}$${\displaystyle (\,8\,)}$${\displaystyle (\,9\,7\,6\,)}$

В качестве первого следствия, число п-перестановки с точно K слева-направо максимумами также равно не имеющие маркировки Стирлинга числом первого рода , . Кроме того, отображение Фоаты принимает n -перестановку с k -слабыми выходами на n -перестановки с k - 1 восхождением. ^[39] Например, (2) (31) = 321 имеет два слабых остатка (с индексом 1 и 2), тогда как f (321) = 231 имеет одно восхождение (с индексом 1, то есть от 2 до 3).${\displaystyle c(n,k)}$

Перестановки полностью упорядоченных множеств [ править ]

В некоторых приложениях элементы переставляемого набора будут сравниваться друг с другом. Это требует, чтобы набор S имел общий порядок, чтобы можно было сравнивать любые два элемента. Набор {1, 2, ..., n } полностью упорядочен обычным отношением «≤», поэтому он является наиболее часто используемым набором в этих приложениях, но в целом подойдет любой полностью упорядоченный набор. В этих приложениях вид упорядоченной компоновки перестановки необходим, чтобы говорить о позициях в перестановке.

Есть целый ряд свойств, которые непосредственно связаны с общим упорядочением S .

Подъемы, спуски, спуски и бега [ править ]

Подъем перестановок  сг из п является любая позиция , я  <  п , где следующее значение больше , чем текущий. То есть, если σ  =  σ ₁ σ ₂ ... σ _n , то i - восхождение, если σ _i  <  σ _{i +1} .

Например, перестановка 3452167 имеет восхождения (в позициях) 1, 2, 5 и 6.

Точно так же спуск - это позиция i  <  n с σ _i  >  σ _{i +1} , поэтому каждый i с либо подъемом, либо спуском  σ .${\displaystyle 1\leq i<n}$

Восходящий запуск перестановки является непустым увеличивая непрерывную подпоследовательность перестановки , которая не может быть продлена на обоих концах; он соответствует максимальной последовательности последовательных восхождений (последний может быть пустым: между двумя последовательными спусками еще есть восходящий пробег длиной 1). Напротив, возрастающая подпоследовательность перестановки не обязательно является непрерывной: это возрастающая последовательность элементов, полученная в результате перестановки путем пропуска значений в некоторых позициях. Например, перестановка 2453167 имеет восходящие прогоны 245, 3 и 167, в то время как она имеет возрастающую подпоследовательность 2367.

Если перестановка имеет k  - 1 спусков, то это должно быть объединение k возрастающих последовательностей . ^[40]

Число перестановок n с k восхождениями является (по определению) числом Эйлера ; это также количество перестановок n с k спусками. Однако некоторые авторы определяют число Эйлера как количество перестановок с k восходящими последовательностями , что соответствует k - 1 спускам. ^[41]${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$

Избыток перестановки σ ₁ σ ₂ ... σ _n - это такой индекс j , что σ _j > j . Если неравенство не строгое (то есть σ _j ≥ j ), то j называется слабым отсутствием . Количество n -перестановок с k выходами совпадает с количеством n -перестановок с k спусками. ^[42]

Инверсии [ править ]

Инверсии перестановок  сг является пара ( я , J ) позиций , где элементы матрицы перестановки находятся в порядке , противоположном: и . ^[44] Таким образом, спуск - это просто инверсия в двух соседних позициях. Например, перестановка σ = 23154 имеет три инверсии: (1, 3), (2, 3) и (4, 5) для пар элементов (2, 1), (3, 1) и ( 5, 4).${\displaystyle i<j}$${\displaystyle \sigma _{i}>\sigma _{j}}$

Иногда инверсия определяется как пара значений ( σ _i , σ _j ) , порядок которых обратный; это не имеет значения для количества инверсий, и эта пара (обратная) также является инверсией в указанном выше смысле для обратной перестановки σ ⁻¹ . Количество инверсий - важная мера того, в какой степени элементы перестановки неупорядочены; то же самое для σ и для σ ⁻¹ . Чтобы привести перестановку с k инверсиями в порядок (то есть преобразовать ее в тождественную перестановку), последовательно применяя (правое умножение на)смежные транспозиции всегда возможны и требуют последовательности из k таких операций. Более того, любой разумный выбор для смежных транспозиций будет работать: достаточно выбрать на каждом шаге транспонирование i и i + 1, где i - спуск перестановки, измененной до сих пор (так что транспонирование удалит этот конкретный спуск, хотя это может создать другие спуски). Это так, потому что применение такой перестановки уменьшает количество инверсий на 1; пока это число не равно нулю, перестановка не является тождеством, поэтому она имеет по крайней мере один спуск. Пузырьковая сортировка и сортировка вставкойможно интерпретировать как отдельные экземпляры этой процедуры, чтобы упорядочить последовательность. Между прочим, эта процедура доказывает, что любую перестановку σ можно записать как произведение смежных транспозиций; для этого можно просто обратить любую последовательность таких перестановок, которая преобразует σ в тождество. Фактически, перечисляя все последовательности смежных транспозиций, которые преобразовали бы σ в идентичность, можно получить (после обращения) полный список всех выражений минимальной длины, записывая σ как произведение смежных транспозиций.

Количество перестановок n с k инверсиями выражается числом Махона ^[45], это коэффициент при X ^k в разложении произведения

${\displaystyle \prod _{m=1}^{n}\sum _{i=0}^{m-1}X^{i}=1\left(1+X\right)\left(1+X+X^{2}\right)\cdots \left(1+X+X^{2}+\cdots +X^{n-1}\right),}$

который также известен (с заменой q на X ) как q-факториал [ n ] _q ! . Расширение продукта появляется в колье (комбинаторика) .

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

Нумерация перестановок [ править ]

Один из способов представления перестановок n - это целое число N с 0 ≤  N  <  n !, При условии, что даны удобные методы для преобразования между числом и представлением перестановки в виде упорядоченного расположения (последовательности). Это дает наиболее компактное представление произвольных перестановок, и в вычислениях особенно привлекательно, когда n достаточно мало, чтобы N можно было хранить в машинном слове; для 32-битных слов это означает n  ≤ 12, а для 64-битных слов это означает n  ≤ 20. Преобразование может быть выполнено через промежуточную форму последовательности чисел d _n , d _{n −1.}, ..., d ₂ , d ₁ , где d _i - неотрицательное целое число, меньшее i (можно опустить d ₁ , поскольку оно всегда равно 0, но его присутствие упрощает описание последующего преобразования в перестановку) . Тогда первым шагом будет просто выразить N в факториальной системе счисления , которая представляет собой просто конкретное смешанное представление системы счисления , где для чисел до n ! основания для последовательных цифр - n , n - 1 , ..., 2, 1. На втором этапе эта последовательность интерпретируется как код Лемера. или (почти то же самое) в виде инверсионной таблицы.

Диаграмма Роте для ${\displaystyle \sigma =(6,3,8,1,4,9,7,2,5)}$

σ я я	1	2	3	4	5	6	7	8	9	Код Лемера
1	×	×	×	×	×	•				d 9 = 5
2	×	×	•							d 8 = 2
3	×	×		×	×		×	•		d 7 = 5
4	•									d 6 = 0
5		×		•						d 5 = 1
6		×			×		×		•	d 4 = 3
7		×			×		•			d 3 = 2
8		•								d 2 = 0
9					•					d 1 = 0
Инверсионный стол	3	6	1	2	4	0	2	0	0

В коде Лемера для перестановки  σ число d _n представляет выбор, сделанный для первого члена  σ ₁ , число d _{n −1} представляет выбор, сделанный для второго члена σ ₂ среди оставшихся n - 1 элементов множества. , и так далее. Точнее, каждый d _{n + 1− i} дает количество оставшихся элементов строго меньшее, чем член σ _i . Поскольку эти оставшиеся элементы обязательно появятся как некоторый более поздний член σ _j , цифраd _{n + 1− i} считает инверсии ( i , j ), включающие i, как меньший индекс (количество значений j, для которых i  <  j и σ _i  >  σ _j ). Таблица инверсии для  σ очень похожа, но здесь d _{n + 1 - k} подсчитывает количество инверсий ( i , j ), где k  =  σ _j встречается как меньшее из двух значений, появляющихся в инвертированном порядке.^[46] Обе кодировки можно визуализироватьпомощью п  по  п Rothe схемы ^[47] (названныйчесть Heinrich августа Роты )в котором точка на ( я , σ _я ) пометить записи перестановки, и крестточке ( я , сг _j ) отмечает инверсию ( i , j ); по определению инверсий крест появляется в любом квадрате, который стоит как перед точкой ( j , σ _j ) в его столбце, так и перед точкой ( i , σ _i) в своем ряду. Код Лемера перечисляет количество крестов в последовательных строках, а таблица инверсии перечисляет количество крестов в последовательных столбцах; это просто код Лемера для обратной перестановки, и наоборот.

Чтобы эффективно преобразовать код Лемера d _n , d _{n −1} , ..., d ₂ , d ₁ в перестановку упорядоченного множества S , можно начать со списка элементов S в порядке возрастания, а для i увеличивая с 1 до n, установите σ _i до элемента в списке, которому предшествуют d _{n + 1− i} других, и удалите этот элемент из списка. Чтобы преобразовать таблицу инверсии d _n , d _{n −1} , ..., d₂ , d ₁ в соответствующую перестановку, можно перемещать числа от d ₁ до d _n , вставляя элементы S от наибольшего к наименьшему в изначально пустую последовательность; на шаге, использующем номер d из таблицы инверсии, элемент из S вставлен в последовательность в точке, где ему предшествуют уже присутствующие d элементов. В качестве альтернативы можно было бы обрабатывать числа из таблицы инверсии и элементы S в обратном порядке, начиная со строки из n пустых слотов, и на каждом шаге размещать элемент из Sв пустой слот, которому предшествуют d других пустых слотов.

Преобразование последовательных натуральных чисел в факториальную систему счисления производит эти последовательности в лексикографическом порядке (как в случае с любой смешанной системой счисления с основанием), а дальнейшее преобразование их в перестановки сохраняет лексикографический порядок, при условии, что используется интерпретация кода Лемера (с использованием таблиц инверсии , каждый получает другой порядок, когда сначала сравнивают перестановки по месту их записей 1, а не по значению их первых записей). Сумма чисел в представлении факториальной системы счисления дает количество инверсий перестановки, а четность этой суммы дает сигнатуруперестановки. Более того, позиции нулей в таблице инверсии дают значения максимумов перестановки слева направо (в примере 6, 8, 9), а позиции нулей в коде Лемера - это позиции правого - минимумы слева (в примере позиционируются 4, 8, 9 значений 1, 2, 5); это позволяет вычислить распределение таких экстремумов среди всех перестановок. Перестановка с кодом Лемера d _n , d _{n −1} , ..., d ₂ , d ₁ имеет восхождение n - i тогда и только тогда, когда d _i ≥ d _{i + 1} .

Алгоритмы генерации перестановок [ править ]

При вычислении может потребоваться сгенерировать перестановки данной последовательности значений. Методы, лучше всего приспособленные для этого, зависят от того, нужны ли какие-то случайно выбранные перестановки или все перестановки, и, в последнем случае, требуется конкретный порядок. Другой вопрос: нужно ли учитывать возможное равенство записей в данной последовательности; если это так, следует только генерировать различные перестановки мультимножества последовательности.

Очевидный способ сгенерировать перестановки n - сгенерировать значения для кода Лемера (возможно, используя представление целых чисел до n в факториальной системе счисления !) И преобразовать их в соответствующие перестановки. Однако последний шаг, хотя и прост, сложно реализовать эффективно, поскольку он требует n операций, каждая из которых - выбор из последовательности и удаление из нее в произвольной позиции; из очевидных представлений последовательности в качестве массива или связанного списка , как требуется (по разным причинам) около п ² /4 операций , чтобы выполнить преобразование. С nвероятно, будет довольно маленьким (особенно если требуется генерация всех перестановок), что не является большой проблемой, но оказывается, что как для случайной, так и для систематической генерации есть простые альтернативы, которые работают значительно лучше. По этой причине не представляется полезным, хотя, безусловно, возможно, использовать специальную структуру данных, которая позволила бы выполнить преобразование из кода Лемера в перестановку за время O ( n log n ) .

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

Для генерации случайных перестановок данной последовательности из n значений не имеет значения, применяет ли кто-либо случайно выбранную перестановку n к последовательности или выбирает случайный элемент из набора различных (мультимножественных) перестановок последовательности. Это потому, что даже если в случае повторяющихся значений может быть много различных перестановок n, которые приводят к одной и той же перестановочной последовательности, количество таких перестановок одинаково для каждого возможного результата. В отличие от систематической генерации, которая становится невозможной для больших n из-за роста числа n !, нет оснований предполагать, что n будет малым для случайной генерации.

Основная идея генерации случайной перестановки - это случайное генерирование одного из n ! последовательности целых чисел d ₁ , d ₂ , ..., d _n, удовлетворяющие 0 ≤ d _i < i (поскольку d ₁ всегда равен нулю, его можно опустить), и преобразовать его в перестановку через биективное соответствие. Для последнего соответствия можно интерпретировать (обратную) последовательность как код Лемера, и это дает метод генерации, впервые опубликованный в 1938 году Рональдом Фишером и Фрэнком Йейтсом . ^[48]Хотя в то время компьютерная реализация не была проблемой, этот метод страдает от описанной выше трудности эффективного преобразования кода Лемера в перестановку. Это можно исправить, используя другое биективное соответствие: после использования d _i для выбора элемента среди i оставшихся элементов последовательности (для уменьшения значений i ) вместо удаления элемента и сжатия последовательности путем смещения других элементов на одно место вниз , один обменэлемент с последним оставшимся элементом. Таким образом, элементы, оставшиеся для выбора, образуют последовательный диапазон в каждый момент времени, даже если они могут не появляться в том же порядке, что и в исходной последовательности. Преобразование последовательности целых чисел в перестановки несколько сложно, но можно увидеть, что каждая перестановка производится точно одним способом, путем непосредственной индукции . Когда выбранный элемент оказывается последним оставшимся элементом, операцию обмена можно не выполнять. Это не происходит достаточно часто, чтобы гарантировать проверку условия, но последний элемент должен быть включен в число кандидатов выбора, чтобы гарантировать, что все перестановки могут быть сгенерированы.

Результирующий алгоритм генерации случайной перестановки может быть описан в псевдокоде следующим образом :a[0], a[1], ..., a[n − 1]

для  i  от  n  до 2 do  d i ← случайный элемент из {0, ..., i - 1} поменять местами  a [ d i ] и a [ i - 1]

Это можно совместить с инициализацией массива следующим образомa[i] = i

для  i  от 0 до  n −1 do  d i +1 ← случайный элемент из {0, ..., i } a [ i ] ← a [ d i +1 ] a [ d i +1 ] ← i

Если d _{i +1} = i , первое присвоение скопирует неинициализированное значение, но второе перезапишет его правильным значением i .

Однако алгоритм Фишера-Йейтса не является самым быстрым алгоритмом для генерации перестановки, поскольку алгоритм Фишера-Йейтса по сути является последовательным алгоритмом, и процедуры «разделяй и властвуй» могут достичь того же результата параллельно. ^[49]

Генерация в лексикографическом порядке [ править ]

Есть много способов систематически генерировать все перестановки заданной последовательности. ^[50] Один классический, простой и гибкий алгоритм основан на поиске следующей перестановки в лексикографическом порядке , если она существует. Он может обрабатывать повторяющиеся значения, в этом случае он генерирует каждую отдельную перестановку мультимножества один раз. Даже для обычных перестановок это значительно эффективнее, чем создание значений для кода Лемера в лексикографическом порядке (возможно, с использованием факториальной системы счисления ) и преобразование их в перестановки. Он начинается с сортировки последовательности по (слабо) возрастаниюпорядка (что дает его лексикографически минимальную перестановку), а затем повторяет переход к следующей перестановке, пока она будет найдена. Этот метод восходит к Нараяне Пандиту в Индии 14 века, и его часто открывали заново. ^[51]

Следующий алгоритм лексикографически генерирует следующую перестановку после данной перестановки. Он изменяет данную перестановку на месте.

1. Найдите наибольший индекс k такой, что a [ k ] < a [ k + 1] . Если такого индекса не существует, перестановка является последней перестановкой.
2. Найдите наибольший индекс l, превышающий k, такой, что a [ k ] < a [ l ] .
3. Поменяйте местами значение a [ k ] на значение a [ l ].
4. Переверните последовательность от a [ k + 1] до последнего элемента a [ n ] включительно .

Например, с учетом последовательности [1, 2, 3, 4] (которая находится в порядке возрастания) и с учетом того, что индекс отсчитывается от нуля , шаги следующие:

1. Индекс к = 2, так как 3 помещается в индекс , который удовлетворяет условию быть наибольший индекс , который по - прежнему меньше , чем в [ K + 1] , который является 4.
2. Индекс l = 3, потому что 4 - единственное значение в последовательности, которое больше 3, чтобы удовлетворять условию a [ k ] < a [ l ].
3. Значения a [2] и a [3] меняются местами, чтобы сформировать новую последовательность [1,2,4,3].
4. Последовательность после k -индекса a [2] до последнего элемента обратная. Поскольку только одно значение находится после этого индекса (3), последовательность в этом случае остается неизменной. Таким образом меняется лексикографический преемник начального состояния: [1,2,4,3].

Следуя этому алгоритму, следующая лексикографическая перестановка будет [1,3,2,4], а 24-я перестановка будет [4,3,2,1], в которой точка a [ k ] < a [ k + 1] будет не существует, что указывает на то, что это последняя перестановка.

Этот метод использует около 3 сравнений и 1,5 перестановки на перестановку, амортизируемых по всей последовательности, не считая начальной сортировки. ^[52]

Генерация с минимальными изменениями [ править ]

Альтернатива вышеупомянутому алгоритму, алгоритм Штейнхауса – Джонсона – Троттера , генерирует упорядочение всех перестановок данной последовательности со свойством, что любые две последовательные перестановки на его выходе отличаются заменой двух соседних значений. Такой порядок перестановок был известен английским звонарем 17-го века, среди которых он был известен как «простые изменения». Одним из преимуществ этого метода является то, что небольшое количество изменений от одной перестановки к другой позволяет реализовать метод за постоянное время на перестановку. То же самое может также легко сгенерировать подмножество четных перестановок, опять же за постоянное время на перестановку, пропуская все остальные перестановки вывода. ^[51]

Альтернативой Штейнхаусу – Джонсону – Троттеру является алгоритм Хипа , ^{[53], который, как} сказал Роберт Седжвик в 1977 году, является самым быстрым алгоритмом генерации перестановок в приложениях. ^[50]

На следующем рисунке показаны выходные данные всех трех вышеупомянутых алгоритмов для генерации всех перестановок длины и шести дополнительных алгоритмов, описанных в литературе.${\displaystyle n=4}$

Упорядочение всех перестановок длины, генерируемых разными алгоритмами. Перестановки обозначены цветом, где${\displaystyle n=4}$  1 ,  2 ,  3 ,  4 . ^[54]

1. Лексикографическая упорядоченность;
2. Алгоритм Штейнхауса – Джонсона – Троттера ;
3. Алгоритм кучи ;
4. Алгоритм перестановки звезды Эрлиха: ^[51] на каждом шаге первая запись перестановки заменяется более поздней записью;
5. Алгоритм изменения префикса Закса: ^[55] на каждом шаге префикс текущей перестановки меняет местами для получения следующей перестановки;
6. Алгоритм Савады-Вильямса: ^[56] каждая перестановка отличается от предыдущей либо циклическим сдвигом влево на одну позицию, либо заменой первых двух записей;
7. Алгоритм Корбетта: ^[57] каждая перестановка отличается от предыдущей циклическим сдвигом влево некоторого префикса на одну позицию;
8. Упорядочение по одной дорожке: ^[58] каждый столбец представляет собой циклический сдвиг других столбцов;
9. Однодорожечный код Грея: ^[58] каждый столбец представляет собой циклический сдвиг других столбцов, плюс любые две последовательные перестановки отличаются только одним или двумя транспозициями.

Меандрические перестановки [ править ]

Меандрические системы порождают меандрические перестановки , особое подмножество альтернативных перестановок . Альтернативная перестановка набора {1, 2, ..., 2 n } - это циклическая перестановка (без фиксированных точек), такая, что цифры в форме циклической записи чередуются между нечетными и четными целыми числами. Меандрические перестановки полезны при анализе вторичной структуры РНК. Не все альтернативные перестановки являются меандрическими. Модификация алгоритма Хипа использовалась для генерации всех альтернативных перестановок порядка n (то есть длины 2 n ) без генерации всех (2 n )! перестановки. ^{[59] [ ненадежный источник? ]} Генерация этих альтернативных перестановок необходима, прежде чем они будут проанализированы, чтобы определить, являются ли они меандрическими или нет.

Алгоритм рекурсивный. В следующей таблице показаны этапы процедуры. На предыдущем шаге были сгенерированы все альтернативные перестановки длины 5. Три копии каждого из них имеют цифру «6», добавленную к правому концу, а затем применяется другое транспонирование, включающее эту последнюю запись, и предыдущую запись в четной позиции (включая идентичность, то есть без транспонирования).

Приложения [ править ]

Перестановки используются в компоненте перемежителя алгоритмов обнаружения и исправления ошибок , таких как турбокоды , например, стандарт мобильной связи 3GPP Long Term Evolution использует эти идеи (см. Техническую спецификацию 3GPP 36.212 ^[60] ). Такие приложения поднимают вопрос о быстрой генерации перестановок, удовлетворяющих определенным желаемым свойствам. Один из методов основан на перестановке многочленов . Также в качестве основы для оптимального хеширования при хешировании уникальной перестановки. ^[61]

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

Примечания [ править ]

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

Библиография [ править ]

• Богарт, Кеннет П. (1990), вводная комбинаторика (2-е изд.), Харкорт Брейс Йованович, ISBN 978-0-15-541576-8
• Бона, Миклош (2004), Комбинаторика перестановок , Chapman Hall-CRC, ISBN 978-1-58488-434-7
• Бона, Миклош (2012), Комбинаторика перестановок (2-е изд.), CRC Press, ISBN 978-1-4398-5051-0
• Бруальди, Ричард А. (2010), Вводная комбинаторика (5-е изд.), Прентис-Холл, ISBN 978-0-13-602040-0
• Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы , Cambridge University Press, ISBN 978-0-521-45761-3
• Кармайкл, Роберт Д. (1956) [1937], Введение в теорию групп конечного порядка , Dover, ISBN 978-0-486-60300-1
• Фрали, Джон Б. (1976), Первый курс абстрактной алгебры (2-е изд.), Чтение: Аддисон-Уэсли , ISBN 0-201-01984-1
• Герштейн, Ларри Дж. (1987), Дискретная математика и алгебраические структуры , WH Freeman and Co., ISBN 978-0-7167-1804-8
• Холл, Маршалл младший (1959), Теория групп , Макмиллан
• Хамфрис, JF (1996), курс теории групп , Oxford University Press, ISBN 978-0-19-853459-4
• Кнут, Дональд (1973), Сортировка и поиск , Искусство компьютерного программирования, 3 В этой книге код Лемера (без использования этого имени) упоминается как вариант C ₁ , ..., C _n таблиц инверсии в упражнении 5.1.1–7 (стр. 19) вместе с двумя другими вариантами.
• Кнут, Дональд (2005), Создание всех кортежей и перестановок , Искусство компьютерного программирования , 4 , Аддисон – Уэсли, ISBN 978-0-201-85393-3 Буклет 2, первая печать.
• Маккой, Нил Х. (1968), Введение в современную алгебру, переработанное издание , Бостон: Аллин и Бэкон , LCCN  68015225
• Неринг, Эвар Д. (1970), Линейная алгебра и теория матриц (2-е изд.), Нью-Йорк: Wiley , LCCN  76091646
• Ротман, Джозеф Дж. (2002), Advanced Modern Algebra , Prentice-Hall, ISBN 978-0-13-087868-7
• Стедман, Фабиан (1677), Campanalogia , Лондон Издатель указан как «WS», который, возможно, был Уильямом Смитом, возможно, действующим как агент Общества молодежи колледжей , которому адресовано «Посвящение». В цитатах первоначальная длинная буква «S» была заменена современной короткой «s».
• Седьмой новый университетский словарь Вебстера , Springfield: G. & C. Merriam Company , 1969

Дальнейшее чтение [ править ]

• Биггс, Норман Л. (2002), Дискретная математика (2-е изд.), Oxford University Press, ISBN 978-0-19-850717-8
• Фоата, Доминик; Schutzenberger, Marcel-Paul (1970), Théorie Géométrique des Polynômes Eulériens , Lecture Notes in Mathematics, 138 , Berlin, Heidelberg: Springer-Verlag, ISBN 978-3-540-04927-2. Ссылка ведет на свободно доступную перепечатанную (LaTeX'ed) и исправленную версию текста, первоначально опубликованную Springer-Verlag.
• Кнут, Дональд (1998), Сортировка и поиск , Искусство компьютерного программирования, 3 (второе издание), Аддисон-Уэсли, ISBN 978-0-201-89685-5. Раздел 5.1: Комбинаторные свойства перестановок, стр. 11–72.
• Седжвик, Роберт (1977). «Методы генерации перестановок». ACM Computing Surveys . 9 (2): 137–164. DOI : 10.1145 / 356689.356692 . S2CID  12139332 .

Внешние ссылки [ править ]

• «Перестановка» , Энциклопедия математики , EMS Press , 2001 [1994]

В Викиверситете есть ресурсы для изучения нотации перестановок

Викискладе есть медиафайлы по теме перестановок .