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

Чтобы узнать о других значениях, см. «Перестановка (значения)» .

«nPr» перенаправляется сюда. Чтобы узнать о других значениях, см. NPR (значения) .

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

В математике перестановка значений набора : может означать одно из двух разных

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

Примером первого значения являются шесть перестановок (упорядочений) набора {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 себя. То есть это функция от S до S , для которой каждый элемент встречается ровно один раз как значение изображения . Такая функция $\sigma :S\to S$ эквивалентно перестановке элементов S , при которой каждый элемент i заменяется соответствующим $\sigma (i)$. Например, перестановка (3, 1, 2) описывается функцией $\sigma$ определяется как

$\sigma (1)=3,\quad \sigma (2)=1,\quad \sigma (3)=2$.

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

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

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

История

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

В Греции Плутарх писал, что Ксенократ Халкидонский (396–314 до н. э.) обнаружил возможное количество различных слогов в греческом языке. Это была бы первая попытка решить сложную задачу перестановками и комбинациями.

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

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

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

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

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

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

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

Перестановки сыграли важную роль в криптоанализе машины «Энигма» , шифровального устройства, использовавшегося нацистской Германией во время Второй мировой войны . В частности, одно важное свойство перестановок, а именно то, что две перестановки являются сопряженными именно тогда, когда они имеют один и тот же тип цикла, было использовано криптологом Марианом Реевским для взлома немецкого шифра «Энигма» на рубеже 1932-1933 годов.

Определение

В текстах по математике перестановки принято обозначать строчными греческими буквами. Обычно либо $\alpha ,\beta ,\gamma$ или $\sigma ,\tau ,\rho ,\pi$ используются.

Перестановку можно определить как биекцию (обратимое отображение, взаимно-однозначную функцию) из множества S в себя:

$\sigma :S\ {\stackrel {\sim }{\longrightarrow }}\ S.$

Тождественная перестановка определяется формулой $\sigma (x)=x$ для всех элементов $x\in S$, и может быть обозначено числом $1$, к ${\text{id}}={\text{id}}_{S}$, или одним 1-циклом (x). Набор всех перестановок набора из n элементов образует симметрическую группу. $S_{n}$, где групповая операция представляет собой композицию функций . Таким образом, для двух перестановок $\sigma$ и $\tau$ в группе $S_{n}$, их продукт $\pi =\sigma \tau$ определяется:

$\pi (i)=\sigma (\tau (i)).$

Состав обычно пишут без точки или другого знака. В общем случае композиция двух перестановок не является коммутативной : $\tau \sigma \neq \sigma \tau .$

Как биекция набора в себя, перестановка — это функция, выполняющая перестановку набора, называемую активной перестановкой или заменой . Более старая точка зрения рассматривает перестановку как упорядоченное расположение или список всех элементов S , называемый пассивной перестановкой (см. § Однострочное обозначение ниже).

Перестановка $\sigma$ можно разложить на один или несколько непересекающихся циклов , которые являются орбитами циклической группы. $\langle \sigma \rangle =\{1,\sigma ,\sigma ^{2},\ldots \}$ действующий на множестве S . Цикл находится путем многократного применения перестановки к элементу: $x,\sigma (x),\sigma (\sigma (x)),\ldots ,\sigma ^{k-1}(x)$, где мы предполагаем $\sigma ^{k}(x)=x$. Цикл, состоящий из k элементов, называется k -циклом. (См. § Обозначение цикла ниже.)

Фиксированная точка перестановки $\sigma$ — это элемент x , взятый в себя, т.е. $\sigma (x)=x$, образуя 1-цикл $(\,x\,)$. Перестановка без неподвижных точек называется расстройством . Перестановка, заменяющая два элемента (один 2-цикл) и оставляющая остальные фиксированными, называется транспозицией .

Обозначения

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

Двухстрочное обозначение

Коши запись Двухстрочная перечисляет элементы S в первой строке и изображение каждого элемента под ним во второй строке. Например, перестановка S = {1, 2, 3, 4, 5, 6}, заданная функцией

$\sigma (1)=2,\ \ \sigma (2)=6,\ \ \sigma (3)=5,\ \ \sigma (4)=4,\ \ \sigma (5)=3,\ \ \sigma (6)=1$

можно записать как

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

Элементы S могут появляться в первой строке в любом порядке, поэтому эту перестановку также можно записать:

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

Однострочное обозначение

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

$\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}}.$

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

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

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

Тогда приведенный выше пример будет:

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

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

Эта компактная форма распространена в элементарной комбинаторике и информатике . Это особенно полезно в приложениях, где перестановки необходимо сравнивать как большие или меньшие, используя лексикографический порядок .

Обозначение цикла

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

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

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

Кроме того, 1-циклы обычно опускают, поскольку из них можно сделать вывод: для любого элемента x в S, не появляющегося ни в одном цикле, неявно предполагается, что $\sigma (x)=x$.

Следуя соглашению об исключении 1-циклов, можно интерпретировать отдельный цикл как перестановку, которая фиксирует все элементы, не входящие в цикл ( циклическая перестановка, имеющая только один цикл длиной больше 1). Тогда список непересекающихся циклов можно рассматривать как композицию этих циклических перестановок. Например, однострочная перестановка $\sigma =265431$ можно записать в обозначениях цикла как:

$\sigma =(126)(35)(4)=(126)(35).$

Это можно рассматривать как композицию $\sigma =\kappa _{1}\kappa _{2}$ циклических перестановок:

$\kappa _{1}=(126)=(126)(3)(4)(5),\quad \kappa _{2}=(35)=(35)(1)(2)(6).$

Хотя перестановки в целом не коммутируют, непересекающиеся циклы коммутируют; например:

$\sigma =(126)(35)=(35)(126).$

Кроме того, каждый цикл можно переписать с другой отправной точки; например,

$\sigma =(126)(35)=(261)(53).$

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

$\sigma ^{-1}=\left({\vphantom {A^{2}}}(126)(35)\right)^{-1}=(621)(53).$

Обозначение канонического цикла

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

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

Например,

(513)(6)(827)(94)

является перестановкой S = {1, 2, . . . , 9} в обозначениях канонического цикла.

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

Состав перестановок

Есть два способа обозначить композицию двух перестановок. В наиболее распространенных обозначениях $\sigma \cdot \tau$ это функция, которая отображает любой элемент x в $\sigma (\tau (x))$. Сначала к аргументу применяется самая правая перестановка: потому что аргумент записывается справа от функции.

Другое . правило умножения перестановок заключается в записи аргумента слева от функции, так что самая левая перестановка действует первой В этих обозначениях перестановку часто записывают в виде показателя степени, поэтому σ, действующая на x , обозначается x ^п ; тогда продукт определяется как $x^{\sigma \cdot \tau }=(x^{\sigma })^{\tau }$. В этой статье используется первое определение, в котором сначала применяется самая правая перестановка.

удовлетворяет Операция композиции функции аксиомам группы . Оно ассоциативно , то есть $(\rho \sigma )\tau =\rho (\sigma \tau )$, а произведения более двух перестановок обычно пишут без скобок. Операция композиции также имеет элемент идентичности (перестановка идентичности ${\text{id}}$), и каждая перестановка $\sigma$ имеет обратную $\sigma ^{-1}$ (его обратная функция ) с $\sigma ^{-1}\sigma =\sigma \sigma ^{-1}={\text{id}}$.

использования термина перестановка

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

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

В старой литературе и элементарных учебниках k -перестановка n (иногда называемая частичной перестановкой , последовательностью без повторения , вариации или расположения ) означает упорядоченное расположение (список) k подмножества -элементов n -множества. Число таких k -перестановок ( k -композиций) $n$ обозначается по-разному такими символами, как $P_{k}^{n}$, $_{n}P_{k}$, $^{n}\!P_{k}$, $P_{n,k}$, $P(n,k)$, или $A_{n}^{k}$, вычисляется по формуле:

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

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

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

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

$P(n,k)={_{n}}P_{k}=(n)_{k}=n^{\underline {k}}.$

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

$C(n,k)={\frac {P(n,k)}{P(k,k)}}={\frac {n^{\underline {k}}}{k!}}={\frac {n!}{(n-k)!\,k!}}.$

Эти числа также известны как биномиальные коэффициенты , обычно обозначаемые ${\tbinom {n}{k}}$:

$C(n,k)={_{n}}C_{k}={\binom {n}{k}}.$

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

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

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

Перестановки без повтора слева, с повтором справа.

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

${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}!}}}.$

Например, количество различных анаграмм слова МИССИСИПИ составляет:

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

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

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

Смотрите также: Циклический порядок § Конечные циклы

Перестановки, если рассматривать их как расположения, иногда называют линейно упорядоченными расположениями. Однако если объекты расположены по кругу, этот особый порядок ослабляется: в расположении нет «первого элемента», поскольку любой элемент можно рассматривать как начало. Расположение различных объектов по кругу называется круговой перестановкой . Их можно формально определить как классы эквивалентности обычных перестановок этих объектов для отношения эквивалентности , создаваемого перемещением последнего элемента линейного расположения вперед.

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

     1           4           2           3
   4   3       2   1       3   4       1   2
     2           3           1           4
 

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

     1          1
   4   3      3   4
     2          2 

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

Свойства

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

Число n -перестановок с k непересекающимися циклами есть беззнаковое число Стирлинга первого рода , обозначаемое $c(n,k)$ или $[{\begin{smallmatrix}n\\k\end{smallmatrix}}]$.

Тип цикла

Циклы (включая неподвижные точки) перестановки $\sigma$набора из n элементов, разделяющего этот набор; поэтому длины этих циклов образуют целочисленное разбиение n ( , которое называется типом цикла или иногда структурой цикла или формой цикла ) $\sigma$. В типе цикла имеется цифра «1» для каждой фиксированной точки $\sigma$, «2» для каждой транспозиции и так далее. Тип цикла $\beta =(1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)$ является $(3,2,2,1).$

Это также можно записать в более компактной форме: [1 ¹ 2 ² 3 ¹ ] . Точнее, общая форма $[1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}]$, где $\alpha _{1},\ldots ,\alpha _{n}$– количество циклов соответствующей длины. Число перестановок данного типа цикла равно

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

Количество типов циклов набора из n элементов равно значению статистической суммы $p(n)$.

Polya Полином индекса цикла — это производящая функция , которая подсчитывает перестановки по типу цикла.

Сопряженные перестановки

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

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

Порядок перестановки $\sigma$ — наименьшее целое положительное число m , так что $\sigma ^{m}=\mathrm {id}$. Это наименьшее общее кратное длин его циклов. Например, порядок $\sigma =(152)(34)$ является ${\text{lcm}}(3,2)=6$.

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

Основная статья: Четность перестановки

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

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

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

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

Знак перестановки равен определителю ее матрицы перестановок (ниже).

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

Основная статья: Матрица перестановок

Матрица перестановок — это размера n × n матрица , которая имеет ровно одну запись 1 в каждом столбце и каждой строке, а все остальные записи равны 0. Существует несколько способов присвоить матрицу перестановок перестановке {1, 2, .. ., н }. Один естественный подход состоит в том, чтобы определить $L_{\sigma }$ быть преобразованием линейным $\mathbb {R} ^{n}$ который меняет стандартный базис $\{\mathbf {e} _{1},\ldots ,\mathbf {e} _{n}\}$ к $L_{\sigma }(\mathbf {e} _{j})=\mathbf {e} _{\sigma (j)}$и определить $M_{\sigma }$быть его матрицей. То есть, $M_{\sigma }$ есть свой j ^й столбец, равный вектор-столбцу n × 1 $\mathbf {e} _{\sigma (j)}$: его запись ( i , j ) равна 1, если i = σ ( j ), и 0 в противном случае. Поскольку композиция линейных отображений описывается умножением матриц, отсюда следует, что эта конструкция совместима с композицией перестановок:

$M_{\sigma }M_{\tau }=M_{\sigma \tau }$.

Например, однострочные перестановки $\sigma =213,\ \tau =231$ есть продукт $\sigma \tau =132$, и соответствующие матрицы:

$$M_{\sigma }M_{\tau }={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}={\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}=M_{\sigma \tau }.$$

Композиция перестановок, соответствующая умножению матриц перестановок.

В литературе также часто встречается обратное соглашение, когда перестановка σ связана с матрицей $P_{\sigma }=(M_{\sigma })^{-1}=(M_{\sigma })^{T}$чья ( i , j запись ) равна 1, если j = σ ( i ), и равна 0 в противном случае. В этом соглашении матрицы перестановок умножаются в порядке, противоположном перестановкам, то есть: $P_{\sigma }P_{\tau }=P_{\tau \sigma }$. В этом соответствии матрицы перестановок действуют в правой части стандарта $1\times n$ векторы-строки $({\bf {e}}_{i})^{T}$: $({\bf {e}}_{i})^{T}P_{\sigma }=({\bf {e}}_{\sigma (i)})^{T}$.

Таблица Кэли справа показывает эти матрицы для перестановок трех элементов.

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

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

Ряд свойств перестановки напрямую связан с общим упорядочением S, если рассматривать перестановку, записанную в однострочной записи, как последовательность $\sigma =\sigma (1)\sigma (2)\cdots \sigma (n)$.

Подъёмы, спуски, пробеги, превышения, рекорды

Восхождением , перестановки σ числа n является любая позиция i < n где следующее значение больше текущего. То есть я — восхождение, если $\sigma (i)<\sigma (i{+}1)$. Например, перестановка 3452167 имеет подъемы (в позициях) 1, 2, 5 и 6.

Аналогично, спуск — это позиция i < n с $\sigma (i)>\sigma (i{+}1)$, поэтому каждый я с $1\leq i<n$ это либо подъем, либо спуск.

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

Если перестановка имеет k - 1 спусков, то она должна быть объединением k восходящих серий.

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

Превышением перестановки σ ₁ σ ₂ ... σ _n называется индекс j такой, что σ _j > j . Если неравенство не является строгим (т. е. σ _j ≥ j ), то j называется слабым превышением . Число n -перестановок с k превышениями совпадает с количеством n -перестановок с k спусками.

Запись σ или максимум слева направо перестановки σ — это элемент i такой, что ( j ) < σ ( i ) для всех j < i .

Фоаты

преобразует Фоаты Фундаментальная биекция перестановку $\sigma$ с заданной формой канонического цикла в перестановку $f(\sigma )={\hat {\sigma }}$ однострочное обозначение которого имеет ту же последовательность элементов с удаленными круглыми скобками. Например:

$\sigma =(513)(6)(827)(94)={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\3&7&5&9&1&6&8&2&4\end{pmatrix}},$ ${\hat {\sigma }}=513682794={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\5&1&3&6&8&2&7&9&4\end{pmatrix}}.$

Здесь первый элемент в каждом каноническом цикле $\sigma$ становится записью (максимум слева направо) ${\hat {\sigma }}$. Данный ${\hat {\sigma }}$, можно найти его записи и вставить круглые скобки для построения обратного преобразования $\sigma =f^{-1}({\hat {\sigma }})$. Подчеркивание записей в приведенном выше примере: ${\hat {\sigma }}={\underline {5}}\,1\,3\,{\underline {6}}\,{\underline {8}}\,2\,7\,{\underline {9}}\,4$, что позволяет восстановить циклы $\sigma$.

В следующей таблице показаны ${\hat {\sigma }}$ и $\sigma$ для шести перестановок S = {1, 2, 3}, с жирным текстом на каждой стороне, показывающим обозначения, используемые в биекции: однострочное обозначение для ${\hat {\sigma }}$ и обозначение канонического цикла для $\sigma$.

${\hat {\sigma }}=f(\sigma )$	$\sigma =f^{-1}({\hat {\sigma }})$
$\mathbf {123} =(\,1\,)(\,2\,)(\,3\,)$	$123=\mathbf {(\,1\,)(\,2\,)(\,3\,)}$
$\mathbf {132} =(\,1\,)(\,3\,2\,)$	$132=\mathbf {(\,1\,)(\,3\,2\,)}$
$\mathbf {213} =(\,2\,1\,)(\,3\,)$	$213=\mathbf {(\,2\,1\,)(\,3\,)}$
$\mathbf {231} =(\,3\,1\,2\,)$	$321=\mathbf {(\,2\,)(\,3\,1\,)}$
$\mathbf {312} =(\,3\,2\,1\,)$	$231=\mathbf {(\,3\,1\,2\,)}$
$\mathbf {321} =(\,2\,)(\,3\,1\,)$	$312=\mathbf {(\,3\,2\,1\,)}$

В качестве первого следствия количество n -перестановок с ровно k записями равно количеству n -перестановок с ровно k циклами: это последнее число является беззнаковым числом Стирлинга первого рода , $c(n,k)$. Более того, отображение Фоаты переводит n -перестановку с k слабыми превышениями в n -перестановку с k - 1 подъемами. Например, (2)(31) = 321 имеет k = 2 слабых превышения (при индексе 1 и 2), тогда как f (321) = 231 имеет k − 1 = 1 подъем (при индексе 1, т. е. от 2 до 3).

Инверсии

Основная статья: Инверсия (дискретная математика)

В головоломке «15» цель состоит в том, чтобы расположить квадраты в порядке возрастания. Начальные позиции, имеющие нечетное количество инверсий, решить невозможно.

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

Иногда инверсию определяют как пару значений ( σ ( i ), σ ( j )); это не имеет значения для количества инверсий, а обратная пара ( σ ( j ), σ ( i )) является инверсией в указанном выше смысле для обратной перестановки σ ⁻¹ .

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

Число перестановок n с k инверсиями выражается числом Маона . Это коэффициент $q^{k}$ в расширении продукта

$$[n]_{q}!=\prod _{m=1}^{n}\sum _{i=0}^{m-1}q^{i}=1\left(1+q\right)\left(1+q+q^{2}\right)\cdots \left(1+q+q^{2}+\cdots +q^{n-1}\right),$$

Обозначения $[n]_{q}!$обозначает q-факториал . Это расширение обычно появляется при изучении ожерелий .

Позволять $\sigma \in S_{n},i,j\in \{1,2,\dots ,n\}$ такой, что $i<j$ и $\sigma (i)>\sigma (j)$. В этом случае назовите вес инверсии $(i,j)$ является $\sigma (i)-\sigma (j)$. Кобаяши (2011) доказал формулу пересчета.

$$\sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{ is bigrassmannian}}\}$$

где $\leq$обозначает порядок Брюа в симметрических группах . Этот градуированный частичный порядок часто появляется в контексте групп Кокстера .

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

Перестановки нумерации

Один из способов представить перестановки 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 - 1 )! , ( п − 2)! , ..., 2!, 1!. Второй шаг интерпретирует эту последовательность как код Лемера или (почти то же самое) как таблицу инверсии.

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

σ я я	1	2	3	4	5	6	7	8	9	Код Лемера
1	×	×	×	×	×	•				д 9 = 5
2	×	×	•							д 8 = 2
3	×	×		×	×		×	•		d 7 = 5
4	•									д 6 = 0
5		×		•						д 5 = 1
6		×			×		×		•	д 4 = 3
7		×			×		•			д 3 = 2
8		•								д2 = 0
9					•					д 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 и σ _я > σ _j ). Таблица инверсий для σ очень похожа, но здесь d _{n +1− k} подсчитывает количество инверсий ( i , j ), где k = σ _j встречается как меньшее из двух значений, появляющихся в инвертированном порядке.

Обе кодировки можно визуализировать с помощью n на n. диаграммы Роте (названный в честь Генриха Августа Роте ( i , σi _{) ,} ) отмечают элементы перестановки, а крестик в ( i , σj _j ) отмечает инверсию ( i , в котором точки в ); по определению инверсии крест появляется в любом квадрате, который стоит как перед точкой ( 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 операций выбора из последовательности и удаления из нее в произвольной позиции; Из очевидных представлений последовательности в виде массива или связанного списка оба требуют (по разным причинам) около n ² /4 операции для выполнения преобразования. Поскольку n , скорее всего, довольно мало (особенно если требуется генерация всех перестановок), это не такая уж большая проблема, но оказывается, что как для случайной, так и для систематической генерации существуют простые альтернативы, которые работают значительно лучше. По этой причине не представляется полезным, хотя, безусловно, возможным использовать специальную структуру данных, которая позволила бы выполнить преобразование из кода Лемера в перестановку за время O ( n log n ) .

Случайное создание перестановок

Основная статья: Перетасовка Фишера-Йейтса

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

Основная идея создания случайной перестановки состоит в том, чтобы сгенерировать случайную одну из n ! последовательности целых чисел d ₁ , d ₂ ,..., d _n , удовлетворяющие 0 ≤ d _i < i (поскольку d ₁ всегда равно нулю, его можно опустить) и преобразовать его в перестановку посредством биективного соответствия. Для последнего соответствия можно интерпретировать (обратную) последовательность как код Лемера, и это дает метод генерации, впервые опубликованный в 1938 году Рональдом Фишером и Фрэнком Йейтсом . Хотя в то время компьютерная реализация не была проблемой, этот метод страдает от описанной выше трудности эффективного преобразования кода Лемера в перестановку. Это можно исправить, используя другое биективное соответствие: после использования 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  } 
      а  [  я  ] ←  а  [  d  я  +1  ] 
      а  [  d  я  +1  ] ←  я 

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

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

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

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

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

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

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

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

Генерация с минимальными изменениями

Основные статьи: алгоритм Штейнхауса – Джонсона – Троттера и алгоритм Хипа.

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

Альтернативой Штейнхаусу-Джонсону-Троттеру является алгоритм Хипа , сказал Роберт Седжвик в 1977 году как самый быстрый алгоритм генерации перестановок в приложениях.

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

Упорядочение всех перестановок длины $n=4$генерируется разными алгоритмами. Перестановки имеют цветовую кодировку, где   1 ,   2 ,   3 ,   4 .

1. Лексикографическая упорядоченность;
2. алгоритм Штейнгауза-Джонсона-Троттера ;
3. Алгоритм Хипа ;
4. Алгоритм перестановки звезд Эрлиха: на каждом этапе первая запись перестановки заменяется последующей записью;
5. Алгоритм перестановки префикса Закса: на каждом этапе префикс текущей перестановки меняется на противоположный для получения следующей перестановки;
6. Алгоритм Савады-Вильямса: каждая перестановка отличается от предыдущей либо циклическим сдвигом влево на одну позицию, либо заменой первых двух записей;
7. Алгоритм Корбетта: каждая перестановка отличается от предыдущей циклическим сдвигом влево некоторого префикса на одну позицию;
8. Однопутный заказ: каждый столбец представляет собой циклический сдвиг других столбцов;
9. Однодорожечный код Грея: каждый столбец представляет собой циклический сдвиг других столбцов, плюс любые две последовательные перестановки отличаются только одной или двумя транспозициями.
10. Алгоритм генерации вложенных свопов по шагам, связанным с вложенными подгруппами $S_{k}\subset S_{k+1}$. Каждая перестановка получается из предыдущей транспонированием влево. Алгоритм связан с Factorial_number_system индекса.

Генерация перестановок во вложенных шагах подкачки

Явная последовательность перестановок (транспозиции, 2-циклы $(pq)$), описывается здесь, причем каждая замена, примененная (слева) к предыдущей цепочке, обеспечивает новую перестановку, так что все перестановки можно получить, каждую только один раз. Эта процедура подсчета/генерации имеет дополнительную структуру (назовем ее вложенной), так как она представлена ​​поэтапно: после полного получения $S_{k-1}$, продолжить поиск $S_{k}\backslash S_{k-1}$ по смежным классам $S_{k-1}\tau _{i}$ из $S_{k-1}$ в $S_{k}$, соответствующим выбором представителей смежного класса $\tau _{i}$будет описано ниже. Обратите внимание, что поскольку каждый $S_{m}$ генерируется последовательно, имеется последний элемент $\lambda _{m}\in S_{m}$. Итак, после генерации $S_{k-1}$ путем обмена, следующая перестановка в $S_{k}\backslash S_{k-1}$ должно быть $\tau _{1}=(p_{1}k)\lambda _{k-1}$ для некоторых $1\leq p_{1}<k$. Затем все свопы, которые сгенерировали $S_{k-1}$ повторяются, генерируя весь смежный класс $S_{k-1}\tau _{1}$, достигая последней перестановки в этом смежном классе $\lambda _{k-1}\tau _{1}$; следующая замена должна переместить перестановку к представителю другого смежного класса $\tau _{2}=(p_{2}k)\lambda _{k-1}\tau _{1}$.

Продолжая таким же образом, получим представителей смежных классов $\tau _{j}=(p_{j}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{i}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{1}k)\lambda _{k-1}$ для однокурсников $S_{k-1}$ в $S_{k}$; заказанный набор $(p_{1},\ldots ,p_{k-1})$ ( $0\leq p_{i}<k$) называется множеством начал смежного класса. Два из этих представителей находятся в одном смежном классе тогда и только тогда, когда $\tau _{j}(\tau _{i})^{-1}=(p_{j}k)\lambda _{k-1}(p_{j-1}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{i+1}k)=\varkappa _{ij}\in S_{k-1}$, то есть, $\varkappa _{ij}(k)=k$. В заключение, перестановки $\tau _{i}\in S_{k}-S_{k-1}$ все являются представителями различных смежных классов тогда и только тогда, когда для любого $k>j>i\geq 1$, $(\lambda _{k-1})^{j-i}p_{i}\neq p_{j}$(без условия повтора). В частности, для того, чтобы все сгенерированные перестановки были различны, не обязательно, чтобы $p_{i}$значения должны быть разными. В процессе это получается $\lambda _{k}=\lambda _{k-1}(p_{k-1}k)\lambda _{k-1}(p_{k-2}k)\lambda _{k-1}\cdots \lambda _{k-1}(p_{1}k)\lambda _{k-1}$ и это обеспечивает процедуру рекурсии.

ПРИМЕРЫ: очевидно, для $\lambda _{2}$ надо $\lambda _{2}=(12)$; строить $\lambda _{3}$существует только две возможности для начала смежного класса, удовлетворяющего условию отсутствия повторения; выбор $p_{1}=p_{2}=1$ приводит к $\lambda _{3}=\lambda _{2}(13)\lambda _{2}(13)\lambda _{2}=(13)$. Чтобы продолжить создание $S_{4}$ нужны соответствующие начала смежных классов (удовлетворяющие условию отсутствия повторения): есть удобный выбор: $p_{1}=1,p_{2}=2,p_{3}=3$, что приводит к $\lambda _{4}=(13)(1234)(13)=(1432)$. Затем, чтобы построить $\lambda _{5}$ удобным выбором для начала смежного класса (удовлетворяющего условию отсутствия повторения) является $p_{1}=p_{2}=p_{3}=p_{4}=1$, что приводит к $\lambda _{5}=(15)$.

Из приведенных выше примеров можно индуктивно перейти к более высоким $k$ аналогичным образом, выбирая начала смежного класса $S_{k}$ в $S_{k+1}$следующим образом: для $k$ даже выбрав все начала смежных классов равными 1 и для $k$ нечетный выбор начала смежного класса, равного $(1,2,\dots ,k)$. При таком выборе «последней» перестановкой является $\lambda _{k}=(1k)$ для $k$ странный и $\lambda _{k}=(1k_{-})(12\cdots k)(1k_{-})$ для $k$ даже ( $k_{-}=k-1$). Используя эти явные формулы, можно легко вычислить перестановку определенного индекса на этапах подсчета/генерации с минимальными вычислениями. Для этого полезно записать индекс в факторной базе. Например, перестановка для индекса $699=5(5!)+4(4!)+1(2!)+1(1!)$ является: $\sigma =\lambda _{2}(13)\lambda _{2}(15)\lambda _{4}(15)\lambda _{4}(15)\lambda _{4}(15)\lambda _{4}(56)\lambda _{5}(46)\lambda _{5}(36)\lambda _{5}(26)\lambda _{5}(16)\lambda _{5}=$ $\lambda _{2}(13)\lambda _{2}((15)\lambda _{4})^{4}(\lambda _{5})^{-1}\lambda _{6}=(23)(14325)^{-1}(15)(15)(123456)(15)=$$(23)(15234)(123456)(15)$, поддавшись наконец, $\sigma =(1653)(24)$.

Поскольку умножение на перестановку подкачки занимает мало времени, а для каждой новой сгенерированной перестановки требуется только одно такое умножение подкачки, эта процедура генерации весьма эффективна. Более того, поскольку существует простая формула, имеющая в каждой последней перестановке $S_{k}$ может сэкономить еще больше времени, чтобы перейти непосредственно к перестановке с определенным индексом за меньшее количество шагов, чем ожидалось, поскольку это можно сделать блоками подгрупп, а не менять местами местами.

Приложения

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

См. также

• Попеременная перестановка
• Свертка
• Циклический порядок
• Четные и нечетные перестановки
• Перестановка Иосифа Флавия
• Символ Леви-Чивита
• Список тем перестановок
• Основной индекс
• Категория перестановки
• Группа перестановок
• Шаблон перестановки
• Представление перестановок (симметричная группа)
• Вероятность
• Номера знакомств
• Сортировочная сеть
• Шифр замены
• Суперпаттерн
• Суперперестановка
• Двенадцатикратный путь
• Слабый порядок перестановок

Библиография

• Богарт, Кеннет П. (1990), Вводная комбинаторика (2-е изд.), Харкорт Брейс Йованович, ISBN  978-0-15-541576-8
• Бона, Миклош (2004), Комбинаторика перестановок , Чепмен Холл-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), Комбинаторика: темы, методы, алгоритмы , издательство Кембриджского университета, ISBN  978-0-521-45761-3
• Кармайкл, Роберт Д. (1956) [1937], Введение в теорию групп конечного порядка , Дувр, 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), Теория групп , Макмиллан
• Хамфрис, Дж. Ф. (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), Продвинутая современная алгебра , Прентис-Холл, ISBN  978-0-13-087868-7
• Стедман, Фабиан (1677), Кампаналогия , Лондон. Издателем указано имя «WS», которым мог быть Уильям Смит, возможно, действовавший в качестве агента Общества студенческой молодежи , которому адресовано «Посвящение». В кавычках исходная длинная «S» заменена современной короткой «s».
• Успенский, Джеймс (1937), Введение в математическую вероятность , McGraw-Hill
• Седьмой новый университетский словарь Вебстера , Спрингфилд: G. & C. Merriam Company , 1 969

Дальнейшее чтение

• Биггс, Норман Л. (2002), Дискретная математика (2-е изд.), Oxford University Press, ISBN  978-0-19-850717-8
• Фоата, Доминик; Шутценбергер, Марсель-Поль (1970), Геометрическая теория эйлеровых полиномов , Конспект лекций по математике, том. 138, Берлин, Гейдельберг: Springer-Verlag, ISBN  978-3-540-04927-2 . Ссылка ведет на свободно доступную перепечатанную (в формате LaTeX) и исправленную версию текста, первоначально опубликованного Springer-Verlag.
• Кнут, Дональд (1998), Сортировка и поиск , Искусство компьютерного программирования, том. 3 (второе изд.), Аддисон-Уэсли, ISBN  978-0-201-89685-5 . Раздел 5.1: Комбинаторные свойства перестановок, стр. 11–72.
• Седжвик, Роберт (1977). «Методы генерации перестановок» . Обзоры вычислительной техники ACM . 9 (2): 137–164. дои : 10.1145/356689.356692 . S2CID   12139332 .
• Масато, Кобаяши (2011). «Перечисление биграссмановых перестановок ниже перестановки в порядке Брюа». Заказ . 1 : 131–137.

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

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