Permutation

From Wikipedia for FEVERv2
(Redirected from Permutations)
Jump to navigation Jump to search

For other uses, see Permutation (disambiguation). Permutation_sentence_0

"nPr" redirects here. Permutation_sentence_1

For other uses, see NPR (disambiguation). Permutation_sentence_2

In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. Permutation_sentence_3

The word "permutation" also refers to the act or process of changing the linear order of an ordered set. Permutation_sentence_4

Permutations differ from combinations, which are selections of some members of a set regardless of order. Permutation_sentence_5

For example, written as tuples, there are six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). Permutation_sentence_6

These are all the possible orderings of this three-element set. Permutation_sentence_7

Anagrams of words whose letters are different are also permutations: the letters are already ordered in the original word, and the anagram is a reordering of the letters. Permutation_sentence_8

The study of permutations of finite sets is an important topic in the fields of combinatorics and group theory. Permutation_sentence_9

Permutations are used in almost every branch of mathematics, and in many other fields of science. Permutation_sentence_10

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. Permutation_sentence_11

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. Permutation_sentence_12

In elementary combinatorics, the k-permutations, or partial permutations, are the ordered arrangements of k distinct elements selected from a set. Permutation_sentence_13

When k is equal to the size of the set, these are the permutations of the set. Permutation_sentence_14

History Permutation_section_0

Permutations called hexagrams were used in China in the I Ching (Pinyin: Yi Jing) as early as 1000 BC. Permutation_sentence_15

Al-Khalil (717–786), an Arab mathematician and cryptographer, wrote the Book of Cryptographic Messages. Permutation_sentence_16

It contains the first use of permutations and combinations, to list all possible Arabic words with and without vowels. Permutation_sentence_17

The rule to determine the number of permutations of n objects was known in Indian culture around 1150. Permutation_sentence_18

The Lilavati by the Indian mathematician Bhaskara II contains a passage that translates to: Permutation_sentence_19

In 1677, Fabian Stedman described factorials when explaining the number of permutations of bells in change ringing. Permutation_sentence_20

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. Permutation_sentence_21

He then explains that with three bells there are "three times two figures to be produced out of three" which again is illustrated. Permutation_sentence_22

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". Permutation_sentence_23

He then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three. Permutation_sentence_24

Effectively, this is a recursive process. Permutation_sentence_25

He continues with five bells using the "casting away" method and tabulates the resulting 120 combinations. Permutation_sentence_26

At this point he gives up and remarks: Permutation_sentence_27

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. Permutation_sentence_28

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. Permutation_sentence_29

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. Permutation_sentence_30

In modern mathematics, there are many similar situations in which understanding a problem requires studying certain permutations related to it. Permutation_sentence_31

Definition Permutation_section_1

As a bijection from a set to itself, a permutation is a function that performs a rearrangement of a set, and is not a rearrangement itself. Permutation_sentence_32

An older and more elementary viewpoint is that permutations are the rearrangements themselves. Permutation_sentence_33

To distinguish between these two, the identifiers active and passive are sometimes prefixed to the term permutation, whereas in older terminology substitutions and permutations are used. Permutation_sentence_34

Notations Permutation_section_2

Since writing permutations elementwise, that is, as piecewise functions, is cumbersome, several notations have been invented to represent them more compactly. Permutation_sentence_35

Cycle notation is a popular choice for many mathematicians due to its compactness and the fact that it makes a permutation's structure transparent. Permutation_sentence_36

It is the notation used in this article unless otherwise specified, but other notations are still widely used, especially in application areas. Permutation_sentence_37

Two-line notation Permutation_section_3

In Cauchy's two-line notation, one lists the elements of S in the first row, and for each one its image below it in the second row. Permutation_sentence_38

For instance, a particular permutation of the set S = {1,2,3,4,5} can be written as: Permutation_sentence_39

this means that σ satisfies σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3, and σ(5) = 1. Permutation_sentence_40

The elements of S may appear in any order in the first row. Permutation_sentence_41

This permutation could also be written as: Permutation_sentence_42

or Permutation_sentence_43

One-line notation Permutation_section_4

Under this assumption, one may omit the first row and write the permutation in one-line notation as Permutation_sentence_44

that is, an ordered arrangement of S. Care must be taken to distinguish one-line notation from the cycle notation described below. Permutation_sentence_45

In mathematics literature, a common usage is to omit parentheses for one-line notation, while using them for cycle notation. Permutation_sentence_46

The one-line notation is also called the word representation of a permutation. Permutation_sentence_47

The example above would then be 2 5 4 3 1 since the natural order 1 2 3 4 5 would be assumed for the first row. Permutation_sentence_48

(It is typical to use commas to separate these entries only if some have two or more digits.) Permutation_sentence_49

This form is more compact, and is common in elementary combinatorics and computer science. Permutation_sentence_50

It is especially useful in applications where the elements of S or the permutations are to be compared as larger or smaller. Permutation_sentence_51

Cycle notation Permutation_section_5

Cycle notation describes the effect of repeatedly applying the permutation on the elements of the set. Permutation_sentence_52

It expresses the permutation as a product of cycles; since distinct cycles are disjoint, this is referred to as "decomposition into disjoint cycles". Permutation_sentence_53

Since for every new cycle the starting point can be chosen in different ways, there are in general many different cycle notations for the same permutation; for the example above one has: Permutation_sentence_54

A convenient feature of cycle notation is that one can find a permutation's inverse simply by reversing the order of the elements in the permutation's cycles. Permutation_sentence_55

For example Permutation_sentence_56

Canonical cycle notation (a.k.a. standard form) Permutation_section_6

In some combinatorial contexts it is useful to fix a certain order for the elements in the cycles and of the (disjoint) cycles themselves. Permutation_sentence_57

Miklós Bóna calls the following ordering choices the canonical cycle notation: Permutation_sentence_58

Permutation_unordered_list_0

  • in each cycle the largest element is listed firstPermutation_item_0_0
  • the cycles are sorted in increasing order of their first elementPermutation_item_0_1

For example, (312)(54)(8)(976) is a permutation in canonical cycle notation. Permutation_sentence_59

The canonical cycle notation does not omit one-cycles. Permutation_sentence_60

Richard P. Stanley calls the same choice of representation the "standard representation" of a permutation. Permutation_sentence_61

and Martin Aigner uses the term "standard form" for the same notion. Permutation_sentence_62

Sergey Kitaev also uses the "standard form" terminology, but reverses both choices; that is, each cycle lists its least element first and the cycles are sorted in decreasing order of their least, that is, first elements. Permutation_sentence_63

Composition of permutations Permutation_section_7

Some authors prefer the leftmost factor acting first, but to that end permutations must be written to the right of their argument, often as an exponent, where σ acting on x is written x; then the product is defined by x = (x). Permutation_sentence_64

However this gives a different rule for multiplying permutations; this article uses the definition where the rightmost permutation is applied first. Permutation_sentence_65

Other uses of the term permutation Permutation_section_8

The concept of a permutation as an ordered arrangement admits several generalizations that are not permutations, but have been called permutations in the literature. Permutation_sentence_66

k-permutations of n Permutation_section_9

which is 0 when k > n, and otherwise is equal to Permutation_sentence_67

This usage of the term permutation is closely related to the term combination. Permutation_sentence_68

A k-element combination of an n-set S is a k element subset of S, the elements of which are not ordered. Permutation_sentence_69

By taking all the k element subsets of S and ordering each of them in all possible ways, we obtain all the k-permutations of S. The number of k-combinations of an n-set, C(n,k), is therefore related to the number of k-permutations of n by: Permutation_sentence_70

Permutations with repetition Permutation_section_10

Permutations of multisets Permutation_section_11

For example, the number of distinct anagrams of the word MISSISSIPPI is: Permutation_sentence_71

A k-permutation of a multiset M is a sequence of length k of elements of M in which each element appears a number of times less than or equal to its multiplicity in M (an element's repetition number). Permutation_sentence_72

Circular permutations Permutation_section_12

Permutations, when considered as arrangements, are sometimes referred to as linearly ordered arrangements. Permutation_sentence_73

In these arrangements there is a first element, a second element, and so on. Permutation_sentence_74

If, however, the objects are arranged in a circular manner this distinguished ordering no longer exists, that is, there is no "first element" in the arrangement, any element can be considered as the start of the arrangement. Permutation_sentence_75

The arrangements of objects in a circular manner are called circular permutations. Permutation_sentence_76

These can be formally defined as equivalence classes of ordinary permutations of the objects, for the equivalence relation generated by moving the final element of the linear arrangement to its front. Permutation_sentence_77

Two circular permutations are equivalent if one can be rotated into the other (that is, cycled without changing the relative positions of the elements). Permutation_sentence_78

The following two circular permutations on four letters are considered to be the same. Permutation_sentence_79

The circular arrangements are to be read counterclockwise, so the following two are not equivalent since no rotation can bring one to the other. Permutation_sentence_80

The number of circular permutations of a set S with n elements is (n – 1)!. Permutation_sentence_81

Properties Permutation_section_13

The number of permutations of n distinct objects is n!. Permutation_sentence_82

The number of n-permutations with k disjoint cycles is the signless Stirling number of the first kind, denoted by c(n, k). Permutation_sentence_83

Permutation type Permutation_section_14

Conjugating permutations Permutation_section_15

Permutation order Permutation_section_16

Parity of a permutation Permutation_section_17

Every permutation of a finite set can be expressed as the product of transpositions. Permutation_sentence_84

Although many such expressions for a given permutation may exist, either they all contain an even or an odd number of transpositions. Permutation_sentence_85

Thus all permutations can be classified as even or odd depending on this number. Permutation_sentence_86

Matrix representation Permutation_section_18

One can represent a permutation of {1, 2, ..., n} as an n×n matrix. Permutation_sentence_87

There are two natural ways to do so, but only one for which multiplications of matrices corresponds to multiplication of permutations in the same order: this is the one that associates to σ the matrix M whose entry Mi,j is 1 if i = σ(j), and 0 otherwise. Permutation_sentence_88

The resulting matrix has exactly one entry 1 in each column and in each row, and is called a permutation matrix. Permutation_sentence_89

is a list of these matrices for permutations of 4 elements. Permutation_sentence_90

The Cayley table on the right shows these matrices for permutations of 3 elements. Permutation_sentence_91

Foata's transition lemma Permutation_section_19

Permutations of totally ordered sets Permutation_section_20

In some applications, the elements of the set being permuted will be compared with each other. Permutation_sentence_92

This requires that the set S has a total order so that any two elements can be compared. Permutation_sentence_93

The set {1, 2, ..., n} is totally ordered by the usual "≤" relation and so it is the most frequently used set in these applications, but in general, any totally ordered set will do. Permutation_sentence_94

In these applications, the ordered arrangement view of a permutation is needed to talk about the positions in a permutation. Permutation_sentence_95

There are a number of properties that are directly related to the total ordering of S. Permutation_sentence_96

Ascents, descents, runs and excedances Permutation_section_21

An ascent of a permutation σ of n is any position i < n where the following value is bigger than the current one. Permutation_sentence_97

That is, if σ = σ1σ2...σn, then i is an ascent if σi < σi+1. Permutation_sentence_98

For example, the permutation 3452167 has ascents (at positions) 1, 2, 5, and 6. Permutation_sentence_99

An ascending run of a permutation is a nonempty increasing contiguous subsequence of the permutation that cannot be extended at either end; it corresponds to a maximal sequence of successive ascents (the latter may be empty: between two successive descents there is still an ascending run of length 1). Permutation_sentence_100

By contrast an increasing subsequence of a permutation is not necessarily contiguous: it is an increasing sequence of elements obtained from the permutation by omitting the values at some positions. Permutation_sentence_101

For example, the permutation 2453167 has the ascending runs 245, 3, and 167, while it has an increasing subsequence 2367. Permutation_sentence_102

If a permutation has k − 1 descents, then it must be the union of k ascending runs. Permutation_sentence_103

An excedance of a permutation σ1σ2...σn is an index j such that σj > j. If the inequality is not strict (that is, σj ≥ j), then j is called a weak excedance. Permutation_sentence_104

The number of n-permutations with k excedances coincides with the number of n-permutations with k descents. Permutation_sentence_105

Inversions Permutation_section_22

Main article: Inversion (discrete mathematics) Permutation_sentence_106

An inversion of a permutation σ is a pair (i,j) of positions where the entries of a permutation are in the opposite order: i < j and σ_i > σ_j. Permutation_sentence_107

So a descent is just an inversion at two adjacent positions. Permutation_sentence_108

For example, the permutation σ = 23154 has three inversions: (1,3), (2,3), (4,5), for the pairs of entries (2,1), (3,1), (5,4). Permutation_sentence_109

Sometimes an inversion is defined as the pair of values (σi,σj) itself whose order is reversed; this makes no difference for the number of inversions, and this pair (reversed) is also an inversion in the above sense for the inverse permutation σ. Permutation_sentence_110

The number of inversions is an important measure for the degree to which the entries of a permutation are out of order; it is the same for σ and for σ. Permutation_sentence_111

To bring a permutation with k inversions into order (that is, transform it into the identity permutation), by successively applying (right-multiplication by) adjacent transpositions, is always possible and requires a sequence of k such operations. Permutation_sentence_112

Moreover, any reasonable choice for the adjacent transpositions will work: it suffices to choose at each step a transposition of i and i + 1 where i is a descent of the permutation as modified so far (so that the transposition will remove this particular descent, although it might create other descents). Permutation_sentence_113

This is so because applying such a transposition reduces the number of inversions by 1; as long as this number is not zero, the permutation is not the identity, so it has at least one descent. Permutation_sentence_114

Bubble sort and insertion sort can be interpreted as particular instances of this procedure to put a sequence into order. Permutation_sentence_115

Incidentally this procedure proves that any permutation σ can be written as a product of adjacent transpositions; for this one may simply reverse any sequence of such transpositions that transforms σ into the identity. Permutation_sentence_116

In fact, by enumerating all sequences of adjacent transpositions that would transform σ into the identity, one obtains (after reversal) a complete list of all expressions of minimal length writing σ as a product of adjacent transpositions. Permutation_sentence_117

The number of permutations of n with k inversions is expressed by a Mahonian number, it is the coefficient of X in the expansion of the product Permutation_sentence_118

which is also known (with q substituted for X) as the q-factorial [n]q! Permutation_sentence_119

. Permutation_sentence_120

The expansion of the product appears in Necklace (combinatorics). Permutation_sentence_121

Permutations in computing Permutation_section_23

Numbering permutations Permutation_section_24

One way to represent permutations of n is by an integer N with 0 ≤ N < n!, provided convenient methods are given to convert between the number and the representation of a permutation as an ordered arrangement (sequence). Permutation_sentence_122

This gives the most compact representation of arbitrary permutations, and in computing is particularly attractive when n is small enough that N can be held in a machine word; for 32-bit words this means n ≤ 12, and for 64-bit words this means n ≤ 20. Permutation_sentence_123

The conversion can be done via the intermediate form of a sequence of numbers dn, dn−1, ..., d2, d1, where di is a non-negative integer less than i (one may omit d1, as it is always 0, but its presence makes the subsequent conversion to a permutation easier to describe). Permutation_sentence_124

The first step then is to simply express N in the factorial number system, which is just a particular mixed radix representation, where for numbers up to n! Permutation_sentence_125

the bases for successive digits are n, n − 1, ..., 2, 1. Permutation_sentence_126

The second step interprets this sequence as a Lehmer code or (almost equivalently) as an inversion table. Permutation_sentence_127

In the Lehmer code for a permutation σ, the number dn represents the choice made for the first term σ1, the number dn−1 represents the choice made for the second term σ2 among the remaining n − 1 elements of the set, and so forth. Permutation_sentence_128

More precisely, each dn+1−i gives the number of remaining elements strictly less than the term σi. Permutation_sentence_129

Since those remaining elements are bound to turn up as some later term σj, the digit dn+1−i counts the inversions (i,j) involving i as smaller index (the number of values j for which i < j and σi > σj). Permutation_sentence_130

The inversion table for σ is quite similar, but here dn+1−k counts the number of inversions (i,j) where k = σj occurs as the smaller of the two values appearing in inverted order. Permutation_sentence_131

Both encodings can be visualized by an n by n Rothe diagram (named after Heinrich August Rothe) in which dots at (i,σi) mark the entries of the permutation, and a cross at (i,σj) marks the inversion (i,j); by the definition of inversions a cross appears in any square that comes both before the dot (j,σj) in its column, and before the dot (i,σi) in its row. Permutation_sentence_132

The Lehmer code lists the numbers of crosses in successive rows, while the inversion table lists the numbers of crosses in successive columns; it is just the Lehmer code for the inverse permutation, and vice versa. Permutation_sentence_133

To effectively convert a Lehmer code dn, dn−1, ..., d2, d1 into a permutation of an ordered set S, one can start with a list of the elements of S in increasing order, and for i increasing from 1 to n set σi to the element in the list that is preceded by dn+1−i other ones, and remove that element from the list. Permutation_sentence_134

To convert an inversion table dn, dn−1, ..., d2, d1 into the corresponding permutation, one can traverse the numbers from d1 to dn while inserting the elements of S from largest to smallest into an initially empty sequence; at the step using the number d from the inversion table, the element from S inserted into the sequence at the point where it is preceded by d elements already present. Permutation_sentence_135

Alternatively one could process the numbers from the inversion table and the elements of S both in the opposite order, starting with a row of n empty slots, and at each step place the element from S into the empty slot that is preceded by d other empty slots. Permutation_sentence_136

Converting successive natural numbers to the factorial number system produces those sequences in lexicographic order (as is the case with any mixed radix number system), and further converting them to permutations preserves the lexicographic ordering, provided the Lehmer code interpretation is used (using inversion tables, one gets a different ordering, where one starts by comparing permutations by the place of their entries 1 rather than by the value of their first entries). Permutation_sentence_137

The sum of the numbers in the factorial number system representation gives the number of inversions of the permutation, and the parity of that sum gives the signature of the permutation. Permutation_sentence_138

Moreover, the positions of the zeroes in the inversion table give the values of left-to-right maxima of the permutation (in the example 6, 8, 9) while the positions of the zeroes in the Lehmer code are the positions of the right-to-left minima (in the example positions the 4, 8, 9 of the values 1, 2, 5); this allows computing the distribution of such extrema among all permutations. Permutation_sentence_139

A permutation with Lehmer code dn, dn−1, ..., d2, d1 has an ascent n − i if and only if di ≥ di+1. Permutation_sentence_140

Algorithms to generate permutations Permutation_section_25

In computing it may be required to generate permutations of a given sequence of values. Permutation_sentence_141

The methods best adapted to do this depend on whether one wants some randomly chosen permutations, or all permutations, and in the latter case if a specific ordering is required. Permutation_sentence_142

Another question is whether possible equality among entries in the given sequence is to be taken into account; if so, one should only generate distinct multiset permutations of the sequence. Permutation_sentence_143

An obvious way to generate permutations of n is to generate values for the Lehmer code (possibly using the factorial number system representation of integers up to n! Permutation_sentence_144

), and convert those into the corresponding permutations. Permutation_sentence_145

However, the latter step, while straightforward, is hard to implement efficiently, because it requires n operations each of selection from a sequence and deletion from it, at an arbitrary position; of the obvious representations of the sequence as an array or a linked list, both require (for different reasons) about n/4 operations to perform the conversion. Permutation_sentence_146

With n likely to be rather small (especially if generation of all permutations is needed) that is not too much of a problem, but it turns out that both for random and for systematic generation there are simple alternatives that do considerably better. Permutation_sentence_147

For this reason it does not seem useful, although certainly possible, to employ a special data structure that would allow performing the conversion from Lehmer code to permutation in O(n log n) time. Permutation_sentence_148

Random generation of permutations Permutation_section_26

Main article: Fisher–Yates shuffle Permutation_sentence_149

For generating random permutations of a given sequence of n values, it makes no difference whether one applies a randomly selected permutation of n to the sequence, or chooses a random element from the set of distinct (multiset) permutations of the sequence. Permutation_sentence_150

This is because, even though in case of repeated values there can be many distinct permutations of n that result in the same permuted sequence, the number of such permutations is the same for each possible result. Permutation_sentence_151

Unlike for systematic generation, which becomes unfeasible for large n due to the growth of the number n!, there is no reason to assume that n will be small for random generation. Permutation_sentence_152

The basic idea to generate a random permutation is to generate at random one of the n! Permutation_sentence_153

sequences of integers d1,d2,...,dn satisfying 0 ≤ di < i (since d1 is always zero it may be omitted) and to convert it to a permutation through a bijective correspondence. Permutation_sentence_154

For the latter correspondence one could interpret the (reverse) sequence as a Lehmer code, and this gives a generation method first published in 1938 by Ronald Fisher and Frank Yates. Permutation_sentence_155

While at the time computer implementation was not an issue, this method suffers from the difficulty sketched above to convert from Lehmer code to permutation efficiently. Permutation_sentence_156

This can be remedied by using a different bijective correspondence: after using di to select an element among i remaining elements of the sequence (for decreasing values of i), rather than removing the element and compacting the sequence by shifting down further elements one place, one swaps the element with the final remaining element. Permutation_sentence_157

Thus the elements remaining for selection form a consecutive range at each point in time, even though they may not occur in the same order as they did in the original sequence. Permutation_sentence_158

The mapping from sequence of integers to permutations is somewhat complicated, but it can be seen to produce each permutation in exactly one way, by an immediate induction. Permutation_sentence_159

When the selected element happens to be the final remaining element, the swap operation can be omitted. Permutation_sentence_160

This does not occur sufficiently often to warrant testing for the condition, but the final element must be included among the candidates of the selection, to guarantee that all permutations can be generated. Permutation_sentence_161

The resulting algorithm for generating a random permutation of a, a, ..., a[n − 1] can be described as follows in pseudocode: Permutation_sentence_162

This can be combined with the initialization of the array a[i] = i as follows Permutation_sentence_163

If di+1 = i, the first assignment will copy an uninitialized value, but the second will overwrite it with the correct value i. Permutation_sentence_164

However, Fisher-Yates is not the fastest algorithm for generating a permutation, because Fisher-Yates is essentially a sequential algorithm and "divide and conquer" procedures can achieve the same result in parallel. Permutation_sentence_165

Generation in lexicographic order Permutation_section_27

There are many ways to systematically generate all permutations of a given sequence. Permutation_sentence_166

One classic, simple, and flexible algorithm is based upon finding the next permutation in lexicographic ordering, if it exists. Permutation_sentence_167

It can handle repeated values, for which case it generates each distinct multiset permutation once. Permutation_sentence_168

Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using the factorial number system) and converting those to permutations. Permutation_sentence_169

It begins by sorting the sequence in (weakly) increasing order (which gives its lexicographically minimal permutation), and then repeats advancing to the next permutation as long as one is found. Permutation_sentence_170

The method goes back to Narayana Pandita in 14th century India, and has been rediscovered frequently. Permutation_sentence_171

The following algorithm generates the next permutation lexicographically after a given permutation. Permutation_sentence_172

It changes the given permutation in-place. Permutation_sentence_173

Permutation_ordered_list_1

  1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.Permutation_item_1_2
  2. Find the largest index l greater than k such that a[k] < a[l].Permutation_item_1_3
  3. Swap the value of a[k] with that of a[l].Permutation_item_1_4
  4. Reverse the sequence from a[k + 1] up to and including the final element a[n].Permutation_item_1_5

For example, given the sequence [1, 2, 3, 4] (which is in increasing order), and given that the index is zero-based, the steps are as follows: Permutation_sentence_174

Permutation_ordered_list_2

  1. Index k = 2, because 3 is placed at an index that satisfies condition of being the largest index that is still less than a[k + 1] which is 4.Permutation_item_2_6
  2. Index l = 3, because 4 is the only value in the sequence that is greater than 3 in order to satisfy the condition a[k] < a[l].Permutation_item_2_7
  3. The values of a and a are swapped to form the new sequence [1,2,4,3].Permutation_item_2_8
  4. The sequence after k-index a to the final element is reversed. Because only one value lies after this index (the 3), the sequence remains unchanged in this instance. Thus the lexicographic successor of the initial state is permuted: [1,2,4,3].Permutation_item_2_9

Following this algorithm, the next lexicographic permutation will be [1,3,2,4], and the 24th permutation will be [4,3,2,1] at which point a[k] < a[k + 1] does not exist, indicating that this is the last permutation. Permutation_sentence_175

This method uses about 3 comparisons and 1.5 swaps per permutation, amortized over the whole sequence, not counting the initial sort. Permutation_sentence_176

Generation with minimal changes Permutation_section_28

Main articles: Steinhaus–Johnson–Trotter algorithm and Heap's algorithm Permutation_sentence_177

An alternative to the above algorithm, the Steinhaus–Johnson–Trotter algorithm, generates an ordering on all the permutations of a given sequence with the property that any two consecutive permutations in its output differ by swapping two adjacent values. Permutation_sentence_178

This ordering on the permutations was known to 17th-century English bell ringers, among whom it was known as "plain changes". Permutation_sentence_179

One advantage of this method is that the small amount of change from one permutation to the next allows the method to be implemented in constant time per permutation. Permutation_sentence_180

The same can also easily generate the subset of even permutations, again in constant time per permutation, by skipping every other output permutation. Permutation_sentence_181

An alternative to Steinhaus–Johnson–Trotter is Heap's algorithm, said by Robert Sedgewick in 1977 to be the fastest algorithm of generating permutations in applications. Permutation_sentence_182

Permutation_ordered_list_3

  1. Lexicographic ordering;Permutation_item_3_10
  2. Steinhaus–Johnson–Trotter algorithm;Permutation_item_3_11
  3. Heap's algorithm;Permutation_item_3_12
  4. Ehrlich's star-transposition algorithm: in each step, the first entry of the permutation is exchanged with a later entry;Permutation_item_3_13
  5. Zaks' prefix reversal algorithm: in each step, a prefix of the current permutation is reversed to obtain the next permutation;Permutation_item_3_14
  6. Sawada-Williams' algorithm: each permutation differs from the previous one either by a cyclic left-shift by one position, or an exchange of the first two entries;Permutation_item_3_15
  7. Corbett's algorithm: each permutation differs from the previous one by a cyclic left-shift of some prefix by one position;Permutation_item_3_16
  8. Single-track ordering: each column is a cyclic shift of the other columns;Permutation_item_3_17
  9. Single-track Gray code: each column is a cyclic shift of the other columns, plus any two consecutive permutations differ only in one or two transpositions.Permutation_item_3_18

Meandric permutations Permutation_section_29

Meandric systems give rise to meandric permutations, a special subset of alternate permutations. Permutation_sentence_183

An alternate permutation of the set {1, 2, ..., 2n} is a cyclic permutation (with no fixed points) such that the digits in the cyclic notation form alternate between odd and even integers. Permutation_sentence_184

Meandric permutations are useful in the analysis of RNA secondary structure. Permutation_sentence_185

Not all alternate permutations are meandric. Permutation_sentence_186

A modification of Heap's algorithm has been used to generate all alternate permutations of order n (that is, of length 2n) without generating all (2n)! Permutation_sentence_187

permutations. Permutation_sentence_188

Generation of these alternate permutations is needed before they are analyzed to determine if they are meandric or not. Permutation_sentence_189

The algorithm is recursive. Permutation_sentence_190

The following table exhibits a step in the procedure. Permutation_sentence_191

In the previous step, all alternate permutations of length 5 have been generated. Permutation_sentence_192

Three copies of each of these have a "6" added to the right end, and then a different transposition involving this last entry and a previous entry in an even position is applied (including the identity; that is, no transposition). Permutation_sentence_193

Permutation_table_general_0

Previous setsPermutation_header_cell_0_0_0 Transposition of digitsPermutation_header_cell_0_0_1 Alternate permutationsPermutation_header_cell_0_0_2
1-2-3-4-5-6Permutation_cell_0_1_0 Permutation_cell_0_1_1 1-2-3-4-5-6Permutation_cell_0_1_2
4, 6Permutation_cell_0_2_0 1-2-3-6-5-4Permutation_cell_0_2_1
2, 6Permutation_cell_0_3_0 1-6-3-4-5-2Permutation_cell_0_3_1
1-2-5-4-3-6Permutation_cell_0_4_0 Permutation_cell_0_4_1 1-2-5-4-3-6Permutation_cell_0_4_2
4, 6Permutation_cell_0_5_0 1-2-5-6-3-4Permutation_cell_0_5_1
2, 6Permutation_cell_0_6_0 1-6-5-4-3-2Permutation_cell_0_6_1
1-4-3-2-5-6Permutation_cell_0_7_0 Permutation_cell_0_7_1 1-4-3-2-5-6Permutation_cell_0_7_2
2, 6Permutation_cell_0_8_0 1-4-3-6-5-2Permutation_cell_0_8_1
4, 6Permutation_cell_0_9_0 1-6-3-2-5-4Permutation_cell_0_9_1
1-4-5-2-3-6Permutation_cell_0_10_0 Permutation_cell_0_10_1 1-4-5-2-3-6Permutation_cell_0_10_2
2, 6Permutation_cell_0_11_0 1-4-5-6-3-2Permutation_cell_0_11_1
4, 6Permutation_cell_0_12_0 1-6-5-2-3-4Permutation_cell_0_12_1

Applications Permutation_section_30

Permutations are used in the interleaver component of the error detection and correction algorithms, such as turbo codes, for example 3GPP Long Term Evolution mobile telecommunication standard uses these ideas (see 3GPP technical specification 36.212). Permutation_sentence_194

Such applications raise the question of fast generation of permutations satisfying certain desirable properties. Permutation_sentence_195

One of the methods is based on the permutation polynomials. Permutation_sentence_196

Also as a base for optimal hashing in Unique Permutation Hashing. Permutation_sentence_197

See also Permutation_section_31

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Permutation.