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

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

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

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

.

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

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

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

История

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

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

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

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

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

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

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

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

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

Самый простой пример перестановок - перестановки без повторов, где мы рассматриваем количество возможных способов размещения n элементов в n местах. Факторный имеет особое применение в определении числа перестановок в наборе , который не включает в себя повторы. Число n !, читаемое как «n факториал», - это как раз то количество способов, которыми мы можем переставить n вещей в новый порядок. Например, если у нас есть три фрукта: апельсин, яблоко и груша, мы можем съесть их в указанном порядке или изменить их (например, яблоко, груша, затем апельсин). Тогда точное количество перестановок . Число становится чрезвычайно большим по мере увеличения количества элементов (n).

Аналогичным образом, количество механизмов из г элементов из п объектов считаются частичной перестановкой . Оно записывается как (читается как «n переставить г») и равно числу (также записываемому как ).

Определение

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

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

  1. Закрытие : если и есть, значит, так и есть
  2. Ассоциативность : Для любых трех перестановок ,
  3. Идентичность : существует перестановка идентичности, обозначаемая и определяемая для всех . Для любого ,
  4. Обратимость : для каждой перестановки существует так, что

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

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

Перестановка может быть разложена на один или несколько непересекающихся циклов , то есть орбит , которые находятся путем многократного отслеживания применения перестановки к некоторым элементам. Например, перестановка, определенная с помощью, имеет 1-цикл, а перестановка, определенная с помощью и, имеет 2-цикл (подробности о синтаксисе см. В § Обозначение цикла ниже). В общем случае цикл длины k , то есть состоящий из k элементов, называется k -циклом.

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

Обозначения

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

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

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

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

или

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

Если , скажем , существует "естественный" порядок элементов S , то он используется для первой строки двухстрочной записи:

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

,

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

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

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

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

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

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

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

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

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

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

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

Например, (312) (54) (8) (976) - это перестановка в канонической записи цикла. Обозначение канонических циклов не исключает одноцикловых.

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

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

Есть два способа обозначить композицию двух перестановок. - это функция, которая отображает любой элемент x набора в . Самая правая перестановка применяется к аргументу первой из-за способа написания приложения функции.

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

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

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

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

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

Более слабое значение термина « перестановка» , которое иногда используется в текстах по элементарной комбинаторике, обозначает те упорядоченные расположения, в которых ни один элемент не встречается более одного раза, но без требования использования всех элементов из данного набора. Это не перестановки, за исключением особых случаев, а естественное обобщение концепции упорядоченного расположения. Действительно, это использование часто включает рассмотрение компоновок фиксированной длины  k элементов, взятых из данного набора размера n , другими словами, эти k -перестановки n представляют собой различные упорядоченные расположения k -элементного подмножества n -множества (иногда называемые вариациями или аранжировками в более ранней литературе). Эти объекты также известны как частичные перестановки или последовательности без повторов , термины, которые избегают путаницы с другим, более распространенным значением слова «перестановка». Число таких -permutations из обозначается по- разному такими символами , как , , , , или , и его значение определяется произведением

,

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

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

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

Эти числа также известны как биномиальные коэффициенты и обозначаются .

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

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

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

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

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

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

.

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

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

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

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

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

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

     1          1
   4   3      3   4
     2          2

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

Характеристики

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

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

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

Циклы разбиения перестановок Множество так длин циклов перестановки образуют перегородку из п называется тип цикла из . В типе цикла есть «1» для каждой фиксированной точки σ, «2» для каждой транспозиции и так далее. Тип цикла - (3, 2, 2, 1). Это также можно записать в более компактной форме как [1 1 2 2 3 1 ].

Общий вид:, где - количество циклов соответствующей длины. Количество перестановок определенного типа равно

.

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

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

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

Порядок перестановки - это наименьшее положительное целое число m, чтобы . Это наименьшее общее кратное длины его цикла. Например, порядок является .

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

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

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

Следует, что

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

Матрица перестановок представляет собой п × п матрица , которая имеет ровно одну запись 1 в каждой колонке и в каждом ряду, а все остальные элементы равны 0. Есть несколько различных конвенций , которые можно использовать , чтобы назначить матрицу перестановок до перестановки {1 , 2, ..., n }. Один естественный подход состоит в том, чтобы связать с перестановкой σ матрицу, чей элемент ( i , j ) равен 1, если i = σ ( j ), и 0 в противном случае. Это соглашение имеет два привлекательных свойства: во-первых, произведение матриц и перестановок находится в одном порядке, то есть для всех перестановок σ и π . Во-вторых, если представляет собой стандартный вектор-столбец (вектор с i- й записью, равной 1, а все остальные записи равны 0), то .

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

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

В литературе также часто встречается обратное соглашение, когда перестановка σ связана с матрицей, чей ( i , j ) элемент равен 1, если j = σ ( i ), и 0 в противном случае. В этом соглашении матрицы перестановок умножаются в порядке, обратном перестановкам, то есть для всех перестановок σ и π . В этом соответствии матрицы перестановок действуют путем перестановки индексов стандартных векторов-строк : один имеет .

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

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

Существует связь между однолинейной и канонической нотацией цикла. Рассмотрим перестановку в канонической нотации цикла, если мы удалим ее круглые скобки, мы получим перестановку в однострочной нотации. Лемма Фоата о переходе устанавливает природу этого соответствия как биекции на множестве n -перестановок (на себя). Ричард П. Стэнли называет это соответствие фундаментальной биекцией .

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

Например, в однострочном обозначении 5 - это первый элемент больше 3, поэтому должен быть первый цикл . Тогда 8 - следующий элемент больше 5, значит, второй цикл . Поскольку 9 больше 8, это сам по себе цикл. Наконец, 9 больше, чем все остальные элементы справа, поэтому последний цикл больше .

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

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

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

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

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

Подъемы, спуски, забеги и бега

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

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

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

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

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

Число перестановок n с k восхождениями является (по определению) числом Эйлера ; это также количество перестановок n с k спусками. Однако некоторые авторы определяют число Эйлера как количество перестановок с k восходящими последовательностями , что соответствует k - 1 спускам.

Избыток перестановки σ 1 σ 2 ... σ n - это такой индекс j , что σ j > j . Если неравенство не строгое (то есть σ jj ), то j называется слабым excedance . Количество n -перестановок с k выходами совпадает с количеством n -перестановок с k спусками.

Инверсии

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

Инверсии перестановок  сг является пара ( я , J ) позиций , где элементы матрицы перестановки находятся в порядке , противоположном: и . Таким образом, спуск - это просто инверсия в двух соседних позициях. Например, перестановка σ = 23154 имеет три инверсии: (1, 3), (2, 3) и (4, 5) для пар элементов (2, 1), (3, 1) и ( 5, 4).

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

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

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

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

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

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

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

В коде Лемера для перестановки  σ число d n представляет выбор, сделанный для первого члена  σ 1 , число d n −1 представляет выбор, сделанный для второго члена σ 2 среди оставшихся 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 встречается как меньшее из двух значений, появляющихся в инвертированном порядке. Оба кодировок могут быть визуализированы с помощью п  по  п Роте диаграммы (названный в честь Генриха августа Роте ) , в котором точки на ( я , σ я ) проставляет записи перестановки, и крест на ( я , σ J ) знаков инверсии ( i , j ); по определению инверсий крест появляется в любом квадрате, который стоит как перед точкой ( j , σ j ) в его столбце, так и перед точкой ( i , σ i ) в его строке. Код Лемера перечисляет количество крестов в последовательных строках, в то время как таблица инверсии перечисляет количество крестов в последовательных столбцах; это просто код Лемера для обратной перестановки, и наоборот.

Чтобы эффективно преобразовать код Лемера d n , d n −1 , ..., d 2 , d 1 в перестановку упорядоченного множества S , можно начать со списка элементов S в порядке возрастания, а для i увеличивая от 1 до n, устанавливаем σ i до элемента в списке, которому предшествуют d n + 1− i других, и удаляем этот элемент из списка. Чтобы преобразовать таблицу инверсии d n , d n −1 , ..., d 2 , d 1 в соответствующую перестановку, можно перемещать числа от d 1 до 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 2 , d 1 имеет восхождение n - i тогда и только тогда, когда d id i + 1 .

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

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

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

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

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

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

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

for i from n downto 2 do
    di ← random element of { 0, ..., i − 1 }
    swap a[di] and a[i − 1]

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

for i from 0 to n−1 do
    di+1 ← random element of { 0, ..., i }
    a[i] ← a[di+1]
    a[di+1] ← i

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

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

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

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

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

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

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

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

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

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

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

Предыдущие наборы Транспонирование цифр Альтернативные перестановки
1-2-3-4-5-6 1-2-3-4-5-6
4, 6 1-2-3-6-5-4
2, 6 1-6-3-4-5-2
1-2-5-4-3-6 1-2-5-4-3-6
4, 6 1-2-5-6-3-4
2, 6 1-6-5-4-3-2
1-4-3-2-5-6 1-4-3-2-5-6
2, 6 1-4-3-6-5-2
4, 6 1-6-3-2-5-4
1-4-5-2-3-6 1-4-5-2-3-6
2, 6 1-4-5-6-3-2
4, 6 1-6-5-2-3-4

Приложения

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

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

Примечания

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

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

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

  • Биггс, Норман Л. (2002), Дискретная математика (2-е изд.), Oxford University Press, ISBN 978-0-19-850717-8
  • Фоата, Доминик; Schutzenberger, Marcel-Paul (1970), Théorie Géométrique des Polynômes Eulériens , Lecture Notes in Mathematics, 138 , Berlin, Heidelberg: Springer-Verlag, ISBN 978-3-540-04927-2. Ссылка ведет на свободно распространяемую перепечатанную (LaTeX'ed) и исправленную версию текста, первоначально опубликованного Springer-Verlag.
  • Кнут, Дональд (1998), Сортировка и поиск , Искусство компьютерного программирования, 3 (второе издание), 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 .

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