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

Математическая версия изменения заказа

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

Изучение перестановок как замен n элементов привело к понятию группы как алгебраической структуры благодаря работам Коши (мемуары 1815 года).

Перестановки сыграли важную роль в криптоанализе машины Enigma , шифровального устройства, использовавшегося нацистской Германией во время Второй мировой войны . В частности, одно важное свойство перестановок, а именно, что две перестановки являются сопряженными именно тогда, когда они имеют одинаковый тип цикла, использовалось криптологом Марианом Реевским для взлома немецкого шифра Enigma в 1932-1933 годах. ^{[12] [13]}

Определение

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

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

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

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

${\displaystyle \pi (i)=\sigma (\tau (i)).}$

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

Как биекция множества на себя, перестановка является функцией, которая выполняет перестановку множества, называемую активной перестановкой или заменой . Более старая точка зрения рассматривает перестановку как упорядоченное расположение или список всех элементов S , называемую пассивной перестановкой . ^[17] Согласно этому определению, все перестановки в § Однострочная нотация являются пассивными. Это значение тонко отличается от того, как пассивный (т. е. псевдоним ) используется в Активном и пассивном преобразовании и в других местах, ^{[18] [19]} которые считали бы все перестановки открытыми для пассивной интерпретации (независимо от того, находятся ли они в однострочной нотации, двухстрочной нотации и т. д.).

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

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

Обозначения

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

Двухстрочная нотация

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

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

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

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

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

${\displaystyle \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 , например , ^[b] , то его используют для первой строки двухстрочной записи: ${\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 =\sigma (x_{1})\;\sigma (x_{2})\;\sigma (x_{3})\;\cdots \;\sigma (x_{n})}$,

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \sigma =(126)(35)(4)=(126)(35).}$

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

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

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

${\displaystyle \sigma =(126)(35)=(35)(126).}$

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

${\displaystyle \sigma =(126)(35)=(261)(53).}$

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

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

Каноническая запись цикла

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

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

Например, является перестановкой в ​​канонической циклической записи. ^[26] $${\displaystyle (513)(6)(827)(94)}$$ ${\displaystyle S=\{1,2,\ldots ,9\}}$

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

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

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

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

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

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

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

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

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

${\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 P(n,k)={_{n}}P_{k}=(n)_{k}=n^{\underline {k}}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 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 непересекающимися циклами — это беззнаковое число Стирлинга первого рода , обозначаемое или . ^[40] ${\displaystyle c(n,k)}$ ${\displaystyle [{\begin{smallmatrix}n\\k\end{smallmatrix}}]}$

Тип цикла

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

Это также может быть записано в более компактной форме как [1 ¹ 2 ² 3 ¹ ] . Точнее, общая форма такова , где — числа циклов соответствующей длины. Число перестановок данного типа цикла равно ^[41] ${\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}!}}}$.

Число типов циклов множества из n элементов равно значению функции статистической суммы . ${\displaystyle p(n)}$

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

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

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

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

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

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

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

Этот результат можно расширить так, чтобы присвоить знак , записанный , каждой перестановке. если четно и если нечетно. Тогда для двух перестановок и ${\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.}$

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

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

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

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

Например, однострочные перестановки имеют произведение , а соответствующие матрицы имеют вид: ${\displaystyle \sigma =213,\ \tau =231}$ ${\displaystyle \sigma \tau =132}$ $${\displaystyle 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 }.}$$

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

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

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

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

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

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

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

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

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

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

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

Число перестановок n с k подъемами (по определению) является числом Эйлера ; это также число перестановок n с k спусками. Некоторые авторы, однако, определяют число Эйлера как число перестановок с k восходящими сериями, что соответствует k − 1 спускам. ^[45] ${\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 спусками. ^[46]

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

Лемма перехода Фоата

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

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

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

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

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

Инверсии

В головоломке 15 цель состоит в том, чтобы получить квадраты в порядке возрастания. Начальные позиции, которые имеют нечетное количество инверсий, не могут быть решены. ^[48]

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

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

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

Число перестановок n с k инверсиями выражается числом Махона . ^[50] Это коэффициент в разложении произведения ${\displaystyle q^{k}}$

$${\displaystyle [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),}$$

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

Пусть такое, что и . В этом случае скажем, что вес инверсии равен . Кобаяши (2011) доказал формулу перечисления ${\displaystyle \sigma \in S_{n},i,j\in \{1,2,\dots ,n\}}$ ${\displaystyle i<j}$ ${\displaystyle \sigma (i)>\sigma (j)}$ ${\displaystyle (i,j)}$ ${\displaystyle \sigma (i)-\sigma (j)}$ $${\displaystyle \sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{ is bigrassmannian}}\}}$$

где обозначает порядок Брюа в симметричных группах . Этот градуированный частичный порядок часто появляется в контексте групп Кокстера . ${\displaystyle \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)!, ( n − 2)!, ..., 2!, 1!. Второй шаг интерпретирует эту последовательность как код Лемера или (почти эквивалентно) как таблицу инверсии.

В коде Лемера для перестановки  σ число 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 встречается как меньшее из двух значений, появляющихся в обратном порядке. ^[51]

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

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

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

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

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

для  i  от  n  до 2 сделать  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 .

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

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

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

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

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 -индекса a [2] до конечного элемента переворачивается. Поскольку после этого индекса (3) лежит только одно значение, последовательность в этом случае остается неизменной. Таким образом, лексикографический преемник начального состояния переставляется: [1, 2, 4, 3].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

Смотрите также

• Математический портал

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

Примечания

1. 1 часто используется для представления единичного элемента в некоммутативной группе.
2. Порядок часто подразумевается неявно. Набор целых чисел естественным образом записывается от наименьшего к наибольшему; набор букв записывается в лексикографическом порядке. Для других наборов естественный порядок должен быть указан явно.
3. Точнее, вариации без повторения . Термин все еще распространен в других языках и появляется в современном английском чаще всего в переводе.
4. Естественный порядок в этом примере — это порядок букв в исходном слове.
5. В старых текстах циклическая перестановка иногда использовалась как синоним циклической перестановки , но теперь это не делается. См. Carmichael (1956, стр. 7)

Ссылки

1. Вебстер (1969)
2. Маккой (1968, стр. 152)
3. Неринг (1970, стр. 86)
4. Хит, Томас Литтл (1981). История греческой математики. Нью-Йорк: Dover Publications. ISBN 0-486-24073-8. OCLC  7703465.
5. Бромелинг, Лайл Д. (1 ноября 2011 г.). «Отчет о раннем статистическом выводе в арабской криптологии». The American Statistician . 65 (4): 255–257. doi :10.1198/tas.2011.10191. S2CID  123537702.
6. Биггс, Н. Л. (1979). «Корни комбинаторики». Historia Math . 6 (2): 109–136. doi :10.1016/0315-0860(79)90074-0.
7. Стедман 1677, стр. 4.
8. Стедман 1677, стр. 5.
9. Стедман 1677, стр. 6–7.
10. Стедман 1677, стр. 8.
11. Стедман 1677, стр. 13–18.
12. Реевский, Мариан (1980). «Применение теории перестановок при взломе шифра Энигмы». Applicationes Mathematicae . 16 (4): 543–559. doi : 10.4064/am-16-4-543-559 . ISSN  1233-7234.
13. Кэш, Дэвид (2019). «CMSC 28400 Введение в криптографию Осень 2019 - Заметки № 2: Перестановки и Энигма» (PDF) .
14. Scheinerman, Edward A. (5 марта 2012 г.). "Глава 5: Функции". Mathematics: A Discrete Introduction (3-е изд.). Cengage Learning. стр. 188. ISBN 978-0840049421. Архивировано из оригинала 5 февраля 2020 г. . Получено 5 февраля 2020 г. Для обозначения перестановок принято использовать строчные греческие буквы (особенно π, σ и τ).
15. Ротман 2002, стр. 41
16. Богарт 1990, стр. 487
17. Кэмерон 1994, стр. 29, сноска 3.
18. Conway, John H.; Burgiel, Heidi; Goodman-Strauss, Chaim (2008). The Symmetries of Things . AK Peters. стр. 179. Перестановка — скажем, имен нескольких людей — может рассматриваться как перемещение либо имен, либо людей. Точка зрения псевдонима рассматривает перестановку как присвоение нового имени или псевдонима каждому человеку (от латинского alias = иначе). Альтернативно, с точки зрения алиби мы перемещаем людей в места, соответствующие их новым именам (от латинского alibi = в другом месте.)
19. "Обозначение перестановки - Викиверситет". en.wikiversity.org . Получено 2024-08-04 .
20. Коши, Ал. (январь 1815 г.). «Mémoire Sur le Nombre des Valeurs qu'une Fonction peut acquérir, lorsqu'on y permute de toutes les manières возможные les quantités qu'elle renferme» [Мемуары о количестве значений, которые функция может получить при перестановке внутри нее, в всеми возможными способами, переменными, которые он содержит]. Журнал политехнической школы (на французском языке). 10 :1–28. См. стр. 4.
    • Перевод на английский
21. Вуссинг, Ганс (2007), Генезис концепции абстрактной группы: вклад в историю происхождения абстрактной теории групп, Courier Dover Publications, стр. 94, ISBN 9780486458687В 1815 году Коши впервые использовал свою систему обозначений перестановок, в которой последовательности записываются одна под другой и обе заключаются в скобки.
22. Богарт 1990, стр. 17
23. Герштейн 1987, стр. 217
24. Aigner, Martin (2007). Курс по перечислению . Springer GTM 238. С. 24–25. ISBN 978-3-540-39035-0.
25. Холл 1959, стр. 54
26. Bona 2012, стр. 87 [В книге есть опечатка/ошибка, поскольку указано (45) вместо (54).]
27. Stanley, Richard P. (2012). Перечислительная комбинаторика: Том I, Второе издание . Cambridge University Press. стр. 30, Prop 1.3.1. ISBN 978-1-107-01542-5.
28. Китаев, Сергей (2011). Закономерности в перестановках и словах . Springer Science & Business Media. стр. 119. ISBN 978-3-642-17333-2.
29. Биггс, Норман Л.; Уайт, AT (1979). Группы перестановок и комбинаторные структуры . Cambridge University Press. ISBN 978-0-521-22287-7.
30. Диксон, Джон Д.; Мортимер, Брайан (1996). Группы перестановок . Springer. ISBN 978-0-387-94599-6.
31. Кэмерон, Питер Дж. (1999). Группы перестановок . Cambridge University Press. ISBN 978-0-521-65302-2.
32. Джеррум, М. (1986). «Компактное представление групп перестановок». J. Algorithms . 7 (1): 60–78. doi :10.1016/0196-6774(86)90038-6. S2CID  18896625.
33. "Комбинации и перестановки". www.mathsisfun.com . Получено 2020-09-10 .
34. Weisstein, Eric W. "Перестановка". mathworld.wolfram.com . Получено 10 сентября 2020 г. .
35. Успенский 1937, стр. 18
36. Хараламбидес, Ч. А. (2002). Перечислительная комбинаторика. CRC Press. стр. 42. ISBN 978-1-58488-290-9.
37. Бруальди 2010, с. 46, теорема 2.4.2.
38. Бруальди 2010, стр. 47
39. Бруальди 2010, стр. 39
40. Бона 2012, стр. 97–103.
41. Саган, Брюс (2001), Симметрическая группа (2-е изд.), Springer, стр. 3
42. Хамфрис 1996, стр. 84.
43. Холл 1959, стр. 60
44. Бона 2004, стр. 4 и далее.
45. Бона 2012, стр. 4–5.
46. Бона 2012, стр. 25.
47. Bona 2012, стр. 109–110.
48. Слокум, Джерри; Вайсштейн, Эрик В. (1999). "15 – головоломка". MathWorld . Wolfram Research, Inc . Получено 4 октября 2014 г. .
49. Бона 2004, стр. 43.
50. Bóna 2004, стр. 43 и далее.
51. Кнут 1973, стр. 12.
52. HA Rothe , Sammlung combinatorisch-analytischer Abhandlungen 2 (Лейпциг, 1800), 263–305. Цитируется по Кнуту 1973, с. 14
53. Фишер, РА; Йейтс, Ф. (1948) [1938]. Статистические таблицы для биологических, сельскохозяйственных и медицинских исследований (3-е изд.). Лондон: Oliver & Boyd. С. 26–27. OCLC  14222135.
54. Бахер, А.; Бодини, О.; Хванг, ХК; Цай, ТХ (2017). «Генерация случайных перестановок путем подбрасывания монеты: классические алгоритмы, новый анализ и современная реализация» (ACM Trans. Algorithms 13(2): 24:1–24:43 ред.). стр. 24–43.
55. Sedgewick, R (1977). "Методы генерации перестановок" (PDF) . Computing Surveys . 9 (2): 137–164. doi :10.1145/356689.356692. S2CID  12139332. Архивировано (PDF) из оригинала 21.02.2008.
56. Knuth 2005, стр. 1–26.
57. "std::next_permutation". cppreference.com . 4 декабря 2017 г. . Получено 31 марта 2018 г. .
58. Хип, BR (1963). «Перестановки путем обмена». The Computer Journal . 6 (3): 293–298. doi : 10.1093/comjnl/6.3.293 .
59. Мютце, Торстен; Савада, Джо; Уильямс, Аарон. «Создание перестановок». Сервер комбинаторных объектов . Получено 29 мая 2019 г.
60. Закс, С. (1984). «Новый алгоритм генерации перестановок». BIT Numerical Mathematics . 24 (2): 196–204. doi :10.1007/BF01937486. S2CID  30234652.
61. Савада, Джо; Уильямс, Аарон (2018). «Путь Гамильтона для проблемы сигма-тау». Труды 29-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2018. Новый Орлеан, Луизиана: Общество промышленной и прикладной математики (SIAM). стр. 568–575. doi : 10.1137/1.9781611975031.37 .
62. Корбетт, ПФ (1992). «Графы ротаторов: эффективная топология для многопроцессорных сетей точка-точка». Труды IEEE по параллельным и распределенным системам . 3 (5): 622–626. doi :10.1109/71.159045.
63. Arndt, Jörg (2011). Matters Computational. Идеи, алгоритмы, исходный код . Springer . doi :10.1007/978-3-642-14764-7. ISBN 978-3-642-14763-0.
64. Попп, О. Т. (2002). Быстрая обработка больших перестановок . частное сообщение.
65. "3GPP TS 36.212".
66. Долев, Шломи; Лахиани, Лимор; Хавив, Йиннон (2013). «Уникальное хеширование перестановок». Теоретическая информатика . 475 : 59–65. doi : 10.1016/j.tcs.2012.12.047 .

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

• Богарт, Кеннет П. (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-е изд.), Prentice-Hall, ISBN 978-0-13-602040-0
• Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы , Cambridge University Press, ISBN 978-0-521-45761-3
• Кармайкл, Роберт Д. (1956) [1937], Введение в теорию групп конечного порядка , Довер, ISBN 978-0-486-60300-1
• Фрейли, Джон Б. (1976), Первый курс абстрактной алгебры (2-е изд.), Чтение: Addison-Wesley , 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, Addison–Wesley, ISBN 978-0-201-85393-3Выпуск 2, первое издание.
• Маккой, Нил Х. (1968), Введение в современную алгебру, пересмотренное издание , Бостон: Allyn and Bacon , LCCN  68015225
• Неринг, Эвар Д. (1970), Линейная алгебра и теория матриц (2-е изд.), Нью-Йорк: Wiley , LCCN  76091646
• Ротман, Джозеф Дж. (2002), Современная алгебра , Prentice-Hall, ISBN 978-0-13-087868-7
• Стедман, Фабиан (1677), Кампания , Лондон Издатель указан как "WS", которым, возможно, был Уильям Смит, возможно, действовавший в качестве агента Общества студенческой молодежи , которому адресовано "Посвящение". В кавычках первоначальное длинное "S" было заменено современным коротким "s".
• Успенский, Джеймс (1937), Введение в математическую вероятность, McGraw-Hill
• Седьмой новый университетский словарь Вебстера , Спрингфилд: G. & C. Merriam Company , 1969

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

• Биггс, Норман Л. (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 (второе издание), Addison–Wesley, 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.
• Масато, Кобаяши (2011). «Перечисление перестановок биграссмановых подстановок в порядке Брюа». Порядок . 1 : 131–137.

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

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