Введение
Математическая интерпретация изменения порядка
В математике перестановка множества может означать одно из двух: упорядочение его элементов в последовательность или линейный порядок, либо само действие или процесс изменения линейного порядка упорядоченного множества. Примером первого значения служат шесть перестановок (упорядочений) множества {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.
an arrangement of its members in a sequence or linear order, or
the act or process of changing the linear order of an ordered set. An example of the first meaning, is the six permutations (orderings) of the set {1, 2, 3}: written as tuples, they are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). Anagrams of a word whose letters are all different are also permutations: the letters are already ordered in the original word, and the anagram reorders them. The study of permutations of finite sets is an important topic in combinatorics and group theory. Permutations are used in almost every branch of mathematics and in many other fields of science. In computer science, they are used for analyzing sorting algorithms; in quantum physics, for describing states of particles; and in biology, for describing RNA sequences. The number of permutations of n distinct objects is n factorial, usually written as n!, which means the product of all positive integers less than or equal to n.
В соответствии со вторым значением, перестановка множества S определяется как биекция из S в само себя. То есть это функция из S в S, для которой каждый элемент встречается ровно один раз в качестве значения. Такая функция эквивалентна перестановке элементов S, при которой каждый элемент i заменяется соответствующим ему. Например, перестановка (3, 1, 2) описывается функцией, определяемой как
Совокупность всех перестановок множества образует группу, называемую симметрической группой этого множества. Групповая операция – это композиция функций (выполнение одной перестановки за другой), в результате которой получается другая функция (перестановка). Свойства перестановок не зависят от природы переставляемых элементов, а только от их количества, поэтому часто рассматривают стандартное множество. В элементарной комбинаторике k-перестановки, или частичные перестановки, – это упорядоченные размещения k различных элементов, выбранных из множества. Когда k равно размеру множества, это перестановки в предыдущем смысле.
In elementary combinatorics, the k permutations, or partial permutations, are the ordered arrangements of k distinct elements selected from a set. When k is equal to the size of the set, these are the permutations in the previous sense.
История
Пермутации, называемые гексаграммами, использовались в Китае в И-Цзин (Пиньинь: И-Цзин) еще в 1000 году до н.э. В Греции Плутарх писал, что Ксенократ Халкидонский (396–314 до н.э.) обнаружил количество различных возможных слогов в греческом языке. Это была бы первая зафиксированная попытка решить сложную задачу в области перестановок и сочетаний. Аль-Халил (717–786), арабский математик и криптограф, написал «Книгу криптографических сообщений». В ней впервые использованы перестановки и сочетания для перечисления всех возможных арабских слов с гласными и без них. Правило определения числа перестановок n объектов было известно в индийской культуре примерно в 1150 году н.э. В «Лилавати» индийского математика Бхаскары II содержится отрывок, который переводится следующим образом: «Произведение умножения арифметической прогрессии, начинающейся и увеличивающейся на единицу и продолжающейся до определенного числа членов, будет представлять собой число вариантов с заданными цифрами». В 1677 году Фабиан Стетман описал факториалы, объясняя количество перестановок колоколов при перезвоне. Начиная с двух колоколов: «во-первых, два должны быть упорядочены двумя способами», что он иллюстрирует, показывая 1 2 и 2 1. Затем он объясняет, что с тремя колоколами существует «три раза два возможных расположения из трех», что также иллюстрируется. Его объяснение включает в себя: «исключите 3, и останется 1.2; исключите 2, и останется 1.3; исключите 1, и останется 2.3». Затем он переходит к четырем колоколам и повторяет аргумент об исключении, показывая, что будет четыре различных набора из трех. По сути, это рекурсивный процесс. Он продолжает с пятью колоколами, используя метод «исключения» и составляет таблицу с полученными 120 комбинациями. На этом этапе он сдается и замечает: «Природа этих методов такова, что изменения для одного числа включают в себя изменения для всех меньших чисел, настолько, что полный перебор изменений для одного числа, кажется, формируется путем объединения полных переборов для всех меньших чисел в единое целое». Стетман расширяет рассмотрение перестановок; он переходит к рассмотрению количества перестановок букв алфавита и лошадей из конюшни в 20 голов. Первый случай, когда, казалось бы, не связанные между собой математические вопросы изучались с помощью перестановок, произошел примерно в 1770 году, когда Жозеф Луи Лагранж, изучая полиномиальные уравнения, заметил, что свойства перестановок корней уравнения связаны с возможностями его решения. Эта работа в конечном итоге привела, благодаря работам Эвариста Галуа, к теории Галуа, которая дает полное описание того, что возможно и невозможно в отношении решения полиномиальных уравнений (с одним неизвестным) с помощью радикалов. В современной математике существует множество подобных ситуаций, в которых для понимания проблемы требуется изучение определенных перестановок, связанных с ней. Перестановки сыграли важную роль в криптоанализе машины «Энигма», шифровального устройства, использовавшегося нацистской Германией во время Второй мировой войны. В частности, одно важное свойство перестановок, а именно, что две перестановки сопряжены тогда и только тогда, когда они имеют один и тот же циклический тип, было использовано криптологом Марианом Реевским для взлома немецкого шифра «Энигма» в 1932–1933 годах.
The product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures. In 1677, Fabian Stedman described factorials when explaining the number of permutations of bells in change ringing. Starting from two bells: "first, two must be admitted to be varied in two ways", which he illustrates by showing 1 2 and 2 1. He then explains that with three bells there are "three times two figures to be produced out of three" which again is illustrated. His explanation involves "cast away 3, and 1.2 will remain; cast away 2, and 1.3 will remain; cast away 1, and 2.3 will remain". He then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three. Effectively, this is a recursive process. He continues with five bells using the "casting away" method and tabulates the resulting 120 combinations. At this point he gives up and remarks:
Now the nature of these methods is such, that the changes on one number comprehends the changes on all lesser numbers, insomuch that a compleat Peal of changes on one number seemeth to be formed by uniting of the compleat Peals on all lesser numbers into one entire body;
Stedman widens the consideration of permutations; he goes on to consider the number of permutations of the letters of the alphabet and of horses from a stable of 20. A first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, when Joseph Louis Lagrange, in the study of polynomial equations, observed that properties of the permutations of the roots of an equation are related to the possibilities to solve it. This line of work ultimately resulted, through the work of Évariste Galois, in Galois theory, which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals. In modern mathematics, there are many similar situations in which understanding a problem requires studying certain permutations related to it. Permutations played an important role in the cryptanalysis of the Enigma machine, a cipher device used by Nazi Germany during World War II. In particular, one important property of permutations, namely, that two permutations are conjugate exactly when they have the same cycle type, was used by cryptologist Marian Rejewski to break the German Enigma cipher in turn of years 1932 1933.
Определение
В математических текстах принято обозначать перестановки с помощью малых греческих букв. Обычно используются либо α, либо β. Перестановку можно определить как биекцию (обратимое отображение, функцию «один к одному» и «на») из множества S в само себя: π: S → S. Тождественная перестановка определяется соотношением π(x) = x для всех элементов x, и может быть обозначена числом 1, символом e, или одним 1-циклом (x). Множество всех перестановок множества с n элементами образует симметрическую группу S<sub>n</sub>, где групповой операцией является композиция функций. Таким образом, для двух перестановок π и σ в группе S<sub>n</sub>, их произведение πσ определяется следующим образом: πσ(x) = π(σ(x)). Композиция обычно записывается без точки или другого знака. В общем случае, композиция двух перестановок не является коммутативной:
Как биекция из множества в само себя, перестановка является функцией, которая выполняет переупорядочивание элементов множества, называемое активной перестановкой или подстановкой. Более старый подход рассматривает перестановку как упорядоченное расположение или список всех элементов S, называемый пассивной перестановкой (см. ниже). Перестановку можно разложить на один или несколько непересекающихся циклов, которые являются орбитами циклической группы, действующей на множество S. Цикл находится путем последовательного применения перестановки к элементу: x, π(x), π(π(x)), …, где мы предполагаем, что цикл рано или поздно замкнется. Цикл, состоящий из k элементов, называется k-циклом. (См. ниже.) Фиксированной точкой перестановки является элемент x, который отображается сам на себя, то есть π(x) = x, образуя 1-цикл. Перестановка, не имеющая фиксированных точек, называется деранжментом. Перестановка, меняющая местами два элемента (1-цикл длины 2) и оставляющая остальные фиксированными, называется транспозицией.
Обозначения
Для удобного представления перестановок широко используется несколько обозначений. Запись в виде циклов – популярный выбор, поскольку она компактна и наглядно демонстрирует структуру перестановки. В данной статье, если не оговорено иное, будет использоваться запись в виде циклов.
Состав пермутаций
Есть два способа обозначить композицию двух перестановок. В наиболее распространенном обозначении, – это функция, которая отображает любой элемент x в . При этом правая перестановка применяется к аргументу первой, поскольку аргумент записан справа от функции. Другое правило умножения перестановок заключается в записи аргумента слева от функции, так что левая перестановка действует первой. В этой нотации перестановка часто записывается в виде показателя степени, поэтому σ, действующая на x, записывается как xσ; тогда произведение определяется как . В данной статье используется первое определение, где применяется правая перестановка. Операция композиции функций удовлетворяет аксиомам группы. Она ассоциативна, то есть , и произведения более чем двух перестановок обычно записываются без скобок. Операция композиции также имеет нейтральный элемент (тождественная перестановка ), и для каждой перестановки σ существует обратная перестановка (обратная функция) σ⁻¹, такая что .
because the argument is written to the right of the function. A different rule for multiplying permutations comes from writing the argument to the left of the function, so that the leftmost permutation acts first. In this notation, the permutation is often written as an exponent, so σ acting on x is written xσ; then the product is defined by This article uses the first definition, where the rightmost permutation is applied first. The function composition operation satisfies the axioms of a group. It is associative, meaning , and products of more than two permutations are usually written without parentheses. The composition operation also has an identity element (the identity permutation ), and each permutation has an inverse (its inverse function) with .
Другие значения термина "пермутация"
Концепция перестановки как упорядоченного расположения имеет несколько обобщений, которые также назывались перестановками, особенно в старой литературе.
Пермутации с повторением
Порядочные расположения k элементов множества S, где допускается повторение, называются k-кортежами. Их иногда называют перестановками с повторением, хотя они не являются перестановками в обычном смысле. Их также называют словами над алфавитом S. Если множество S содержит n элементов, число k-кортежей над S равно A. Формальный язык — это множество слов, подчиняющихся заданным правилам.
A formal language is a set of words obeying specified rules.
Свойства
Количество перестановок n различных объектов равно n!. Число перестановок n элементов с k непересекающимися циклами является числом Стирлинга первого рода без знака, обозначаемым или .
Тип цикла
Циклы (включая фиксированные точки) перестановки множества из n элементов разбивают это множество на непересекающиеся подмножества; таким образом, длины этих циклов образуют целочисленный состав числа n, который называется типом цикла (или иногда циклической структурой или циклической формой) перестановки. В типе цикла для каждой фиксированной точки перестановки стоит "1", для каждой транспозиции – "2", и так далее. Тип цикла перестановки is This может быть также записан в более компактной форме как [1^(1)2^(2)3^(1)]. Более точно, общая форма – , где – числа циклов соответствующей длины. Число перестановок заданного типа цикла равно .
This may also be written in a more compact form as [1^(1)2^(2)3^(1)]. More precisely, the general form is , where are the numbers of cycles of respective length. The number of permutations of a given cycle type is
The number of cycle types of a set with n elements equals the value of the partition function
Polya's cycle index polynomial is a generating function which counts permutations by their cycle type.
Число типов циклов множества из n элементов равно значению функции разбиения . Полиномиальный индекс циклов Полиа – это производящая функция, подсчитывающая перестановки по их типу цикла.
This may also be written in a more compact form as [1^(1)2^(2)3^(1)]. More precisely, the general form is , where are the numbers of cycles of respective length. The number of permutations of a given cycle type is
The number of cycle types of a set with n elements equals the value of the partition function
Polya's cycle index polynomial is a generating function which counts permutations by their cycle type.
Конъюгирующие пермутации
В общем, составление перестановок, записанных в циклической нотации, не подчиняется простому шаблону – циклы композиции могут отличаться от исходных циклов. Однако, тип цикла сохраняется в особом случае сопряжения перестановки другой перестановкой , что означает вычисление произведения . Здесь, является сопряженной к относительно , и её циклическая нотация может быть получена путем взятия циклической нотации для и применения к каждому элементу в ней. Следовательно, две перестановки сопряжены тогда и только тогда, когда они имеют одинаковый тип цикла.
Порядок пермутации
Порядок перестановки — наименьшее положительное целое число m, такое что m-я степень перестановки является тождественной. Это наименьшее общее кратное длин её циклов. Например, порядок перестановки (1 2 3) равен 3.
Матричное представление
Матрица перестановок — это матрица n × n, в которой в каждом столбце и в каждой строке ровно одна единица, а все остальные элементы равны нулю. Существует несколько способов сопоставить матрицу перестановке множества {1, 2, …, n}. Один из естественных подходов — определить как линейное преобразование, переставляющее стандартный базис , и определить как его матрицу. То есть, j-й столбец имеет вид n × 1 вектора-столбца: его (i, j)-й элемент равен 1, если i = σ(j), и 0 в противном случае. Поскольку композиция линейных отображений описывается умножением матриц, следует, что эта конструкция согласуется с композицией перестановок: например, однострочные перестановки имеют произведение , а соответствующие матрицы:
В литературе также часто встречается обратное соглашение, при котором перестановка σ сопоставляется матрице, (i, j)-й элемент которой равен 1, если j = σ(i), и 0 в противном случае. В этом соглашении матрицы перестановок умножаются в порядке, обратном порядку перемножения перестановок, то есть . В этом соответствии матрицы перестановок действуют справа на векторы стандартных строк: таблица Кэли справа показывает эти матрицы для перестановок из 3 элементов.
The Cayley table on the right shows these matrices for permutations of 3 elements.
Пермутации полностью упорядоченных множеств
В некоторых приложениях элементы переставляемого множества будут сравниваться между собой. Это требует, чтобы множество S имело полный порядок, позволяющий сравнить любые два его элемента. Множество {1, 2, ..., n} с обычным отношением ≤ является наиболее часто используемым множеством в таких приложениях. Ряд свойств перестановки напрямую связаны с полным упорядочением S, если перестановка представлена в линейной записи в виде последовательности.
Подъемы, спуска, пробеги, превышения, рекорды
Подъем перестановки σ длины n – это любая позиция i < n, где следующее значение больше текущего. То есть, i является подъемом, если, например, перестановка 3452167 имеет подъемы (на позициях) 1, 2, 5 и 6. Аналогично, спуск – это позиция i < n с σ(i+1) < σ(i), поэтому каждое i с 1 ≤ i < n является либо подъемом, либо спуском. Восходящий пробег перестановки – это непустая возрастающая смежная подпоследовательность, которую нельзя расширить ни с одного конца; он соответствует максимальной последовательности последовательных подъемов (последняя может быть пустой: между двумя последовательными спусками все равно существует восходящий пробег длины 1). В отличие от этого, возрастающая подпоследовательность перестановки не обязательно смежна: это возрастающая последовательность, полученная путем пропуска некоторых значений в линейной записи. Например, перестановка 2453167 имеет восходящие пробеги 245, 3 и 167, а также возрастающую подпоследовательность 2367. Если перестановка имеет k - 1 спусков, то она должна быть объединением k восходящих пробегов. Число перестановок длины n с k подъемами является (по определению) эйлеровским числом ; это также число перестановок длины n с k спусками. Некоторые авторы, однако, определяют эйлеровское число как число перестановок с k восходящими пробегами, что соответствует k − 1 спускам. Превышение перестановки σ1σ2…σn – это индекс j, при котором σj > j. Если неравенство нестрогое (то есть σj ≥ j), то j называется слабым превышением. Количество перестановок длины n с k превышениями совпадает с количеством перестановок длины n с k спусками. Рекорд или максимум слева направо перестановки σ – это элемент σ(i), такой что σ(j) < σ(i) для всех j < i.
Алгоритмы для генерации пермутаций
В вычислительной технике может потребоваться генерировать перестановки заданной последовательности значений. Наиболее подходящие методы зависят от того, нужны ли случайно выбранные перестановки или все перестановки, и в последнем случае, требуется ли конкретный порядок. Другой вопрос – следует ли учитывать возможное равенство элементов в заданной последовательности; если да, то следует генерировать только различные перестановки с повторениями. Очевидный способ генерации перестановок для n – это генерировать значения для кода Лемера (возможно, используя факториальную систему счисления для целых чисел до n!), а затем преобразовывать их в соответствующие перестановки. Однако, хотя этот последний шаг и прост, его сложно эффективно реализовать, поскольку он требует n операций, каждая из которых включает выбор элемента из последовательности и удаление его из произвольной позиции; при очевидных представлениях последовательности в виде массива или связного списка, оба требуют (по разным причинам) примерно n²/4 операций для выполнения преобразования. Если n, скорее всего, будет относительно небольшим (особенно если требуется генерация всех перестановок), это не является серьезной проблемой, но оказывается, что для случайной и систематической генерации существуют более простые и эффективные альтернативы. Поэтому не представляется целесообразным, хотя и возможно, использовать специальную структуру данных, позволяющую выполнять преобразование из кода Лемера в перестановку за время O(n log n).
Приложения
Пермутации используются в компоненте перестановки алгоритмов обнаружения и коррекции ошибок, таких как турбокоды. Например, стандарт мобильной телекоммуникации 3GPP Long Term Evolution использует эти идеи (см. техническую спецификацию 3GPP 36.212). Такие приложения ставят вопрос о быстром генерировании пермутаций, обладающих определенными желаемыми свойствами. Один из методов основан на полиномах перестановок. Также они используются в качестве основы для оптимального хеширования в Unique Permutation Hashing.