the act or process of changing the linear order of an ordered set.[1]
An example of the first meaning is the six permutations (orderings) of the set {1, 2, 3}: written astuples, 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 offinite sets is an important topic incombinatorics andgroup theory.
Permutations are used in almost every branch of mathematics and in many other fields of science. Incomputer science, they are used for analyzingsorting algorithms; inquantum physics, for describing states of particles; and inbiology, for describingRNA sequences.
The number of permutations ofn distinct objects isnfactorial, usually written asn!, which means the product of all positive integers less than or equal ton.
According to the second meaning, a permutation of asetS is defined as abijection fromS to itself.[2][3] That is, it is afunction fromS toS for which every element occurs exactly once as animage value. Such a function is equivalent to the rearrangement of the elements ofS in which each elementi is replaced by the corresponding. For example, the permutation (3, 1, 2) corresponds to the function defined asThe collection of all permutations of a set form agroup called thesymmetric group of the set. Thegroup operation is thecomposition of functions (performing one rearrangement after the other), which results in another function (rearrangement).
In elementary combinatorics, thek-permutations, orpartial permutations, are the ordered arrangements ofk distinct elements selected from a set. Whenk is equal to the size of the set, these are the permutations in the previous sense.
In the popular puzzleRubik's Cube invented in 1974 byErnő Rubik, each turn of the puzzle faces creates a permutation of the surface colors.
Permutation-like objects calledhexagrams were used in China in theI Ching (Pinyin: Yi Jing) as early as 1000 BC.
In Greece,Plutarch wrote thatXenocrates of Chalcedon (396–314 BC) discovered the number of different syllables possible in the Greek language. This would have been the first attempt on record to solve a difficult problem in permutations and combinations.[4]
Al-Khalil (717–786), anArab mathematician andcryptographer, wrote theBook of Cryptographic Messages. It contains the first use of permutations and combinations, to list all possibleArabic words with and without vowels.[5]
The rule to determine the number of permutations ofn objects was known in Indian culture around 1150 AD. TheLilavati by the Indian mathematicianBhāskara II contains a passage that translates as follows:
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.[6]
In 1677,Fabian Stedman described factorials when explaining the number of permutations of bells inchange 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.[7] 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".[8] 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.[9] 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;[10]
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.[11]
A first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, whenJoseph Louis Lagrange, in the study of polynomial equations, observed that properties of the permutations of theroots of an equation are related to the possibilities to solve it. This line of work ultimately resulted, through the work ofÉvariste Galois, inGalois 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.
The study of permutations as substitutions on n elements led to the notion of group asalgebraic structure, through the works ofCauchy (1815 memoir).
Permutations played an important role in thecryptanalysis of the Enigma machine, a cipher device used byNazi Germany duringWorld 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 cryptologistMarian Rejewski to break the German Enigma cipher in turn of years 1932-1933.[12][13]
In mathematics texts it is customary to denote permutations using lowercase Greek letters.[14]
A permutation can be defined as abijection (an invertible mapping, a one-to-one and onto function) from a setS to itself:Theidentity permutation is defined by for all elements, and can be denoted by the number,[a] by, or by a single 1-cycle (x).[15][16]
The set of all permutations of a set withn elements forms thesymmetric group, where thegroup operation iscomposition of functions. Thus for two permutations and in the group, their product is defined byComposition is usually written without a dot or other sign. In general, composition of two permutations is notcommutative; that is, typically the permutations and are not equal.
As a bijection from a set to itself, a permutation is a function thatperforms a rearrangement of a set, termed anactive permutation orsubstitution. An older viewpoint sees a permutation as an ordered arrangement or list of all the elements ofS, called apassive permutation.[17] According to this definition, all permutations in§ One-line notation are passive. This meaning is subtly distinct from how passive (i.e.alias) is used inActive and passive transformation and elsewhere,[18][19] which would consider all permutations open to passive interpretation (regardless of whether they are in one-line notation, two-line notation, etc.).
A permutation can be decomposed into one or more disjointcycles which are theorbits of the cyclic groupacting on the setS. A cycle is found by repeatedly applying the permutation to an element:, where we assume . A cycle consisting ofk elements is called ak-cycle. (See§ Cycle notation below.)
Afixed point of a permutation is an elementx which is taken to itself, that is, forming a 1-cycle. A permutation with no fixed points is called aderangement. A permutation exchanging two elements (a single 2-cycle) and leaving the others fixed is called atransposition.
Several notations are widely used to represent permutations conveniently. The properties of permutations do not depend on the nature of the elements being permuted, only on their number, so one often considers the standard set.Cycle notation is a popular choice, as it is compact and shows the permutation's structure clearly. This article will use cycle notation unless otherwise specified.
Cauchy'stwo-line notation[20][21] lists the elements ofS in the first row, and the image of each element below it in the second row. For example, the permutation ofS = {1, 2, 3, 4, 5, 6} given by the function
can be written as
The elements ofS may appear in any order in the first row, so this permutation could also be written:
If there is a "natural" order for the elements ofS,[b] say, then one uses this for the first row of the two-line notation:
Under this assumption, one may omit the first row and write the permutation inone-line notation as
,
that is, as an ordered arrangement of the elements ofS.[22][23] Care must be taken to distinguish one-line notation from the cycle notation described below: a common usage is to omit parentheses or other enclosing marks for one-line notation, while using parentheses for cycle notation. The one-line notation is also called theword representation.[24]
The example above would then be:
(It is typical to use commas to separate these entries only if some have two or more digits.)
Cycle notation describes the effect of repeatedly applying the permutation on the elements of the setS, with an orbit being called acycle. The permutation is written as a list of cycles; since distinct cycles involvedisjoint sets of elements, this is referred to as "decomposition into disjoint cycles".
To write down the permutation in cycle notation, one proceeds as follows:
Write an opening bracket followed by an arbitrary elementx of:
Trace the orbit ofx, writing down the values under successive applications of:
Repeat until the value returns tox, and close the parenthesis without repeatingx:
Continue with an elementy ofS which was not yet written, and repeat the above process:
Repeat until all elements ofS are written in cycles.
Also, it is common to omit 1-cycles, since these can be inferred: for any elementx inS not appearing in any cycle, one implicitly assumes.[25]
Following the convention of omitting 1-cycles, one may interpret an individual cycle as a permutation which fixes all the elements not in the cycle (acyclic permutation having only one cycle of length greater than 1). Then the list of disjoint cycles can be seen as the composition of these cyclic permutations. For example, the one-line permutation can be written in cycle notation as:
This may be seen as the composition of cyclic permutations:
While permutations in general do not commute, disjoint cycles do; for example:
Also, each cycle can be rewritten from a different starting point; for example,
Thus one may write the disjoint cycles of a given permutation in many different ways.A convenient feature of cycle notation is that inverting the permutation is given by reversing the order of the elements in each cycle. For example,
In some combinatorial contexts it is useful to fix a certain order for the elements in the cycles and of the (disjoint) cycles themselves.Miklós Bóna calls the following ordering choices thecanonical cycle notation:
in each cycle thelargest element is listed first
the cycles are sorted inincreasing order of their first element, not omitting 1-cycles
For example, is a permutation of in canonical cycle notation.[26]
Richard Stanley calls this the "standard representation" of a permutation,[27] and Martin Aigner uses "standard form".[24]Sergey Kitaev also uses the "standard form" terminology, but reverses both choices; that is, each cycle lists its minimal element first, and the cycles are sorted in decreasing order of their minimal elements.[28]
There are two ways to denote the composition of two permutations. In the most common notation, is the function that maps any elementx to. The rightmost permutation is applied to the argument first,[29]because the argument is written to the right of the function.
Adifferent rule for multiplying permutations comes from writing the argument to the left of the function, so that the leftmost permutation acts first.[30][31][32]In this notation, the permutation is often written as an exponent, soσ acting onx is writtenxσ; then the product is defined by. This article uses the first definition, where the rightmost permutation is applied first.
Thefunction composition operation satisfies the axioms of agroup. It isassociative, meaning, and products of more than two permutations are usually written without parentheses. The composition operation also has anidentity element (the identity permutation), and each permutation has an inverse (itsinverse function) with.
The concept of a permutation as an ordered arrangement admits several generalizations that have been calledpermutations, especially in older literature.
In older literature and elementary textbooks, ak-permutation ofn (sometimes called apartial permutation,sequence without repetition,variation, orarrangement) means an ordered arrangement (list) of ak-element subset of ann-set.[c][33][34] The number of suchk-permutations (k-arrangements) of is denoted variously by such symbols as,,,,, or,[35] computed by the formula:[36]
,
which is 0 whenk >n, and otherwise is equal to
The product is well defined without the assumption that is a non-negative integer, and is of importance outside combinatorics as well; it is known as thePochhammer symbol or as the-th falling factorial power:
This usage of the termpermutation is closely associated with the termcombination to mean a subset. Ak-combination of a setS is ak-element subset ofS: the elements of a combination are not ordered. Ordering thek-combinations ofS in all possible ways produces thek-permutations ofS. The number ofk-combinations of ann-set,C(n,k), is therefore related to the number ofk-permutations ofn by:
Ordered arrangements ofk elements of a setS, where repetition is allowed, are calledk-tuples. They have sometimes been referred to aspermutations with repetition, although they are not permutations in the usual sense. They are also calledwords orstrings over the alphabetS. If the setS hasn elements, the number ofk-tuples overS is
Permutations without repetition on the left, with repetition to their right
IfM is a finitemultiset, then amultiset permutation is an ordered arrangement of elements ofM in which each element appears a number of times equal exactly to its multiplicity inM. Ananagram of a word having some repeated letters is an example of a multiset permutation.[d] If the multiplicities of the elements ofM (taken in some order) are,, ..., and their sum (that is, the size ofM) isn, then the number of multiset permutations ofM is given by themultinomial coefficient,[37]
For example, the number of distinct anagrams of the word MISSISSIPPI is:[38]
.
Ak-permutation of a multisetM is a sequence ofk elements ofM in which each element appearsa number of times less than or equal to its multiplicity inM (an element'srepetition number).
Permutations, when considered as arrangements, are sometimes referred to aslinearly ordered arrangements. If, however, the objects are arranged in a circular manner this distinguished ordering is weakened: there is no "first element" in the arrangement, as any element can be considered as the start. An arrangement of distinct objects in a circular manner is called acircular permutation.[39][e] These can be formally defined asequivalence classes of ordinary permutations of these objects, for theequivalence relation generated by moving the final element of the linear arrangement to its front.
Two circular permutations are equivalent if one can be rotated into the other. The following four circular permutations on four letters are considered to be the same.
1 4 2 3 4 3 2 1 3 4 1 2 2 3 1 4
The circular arrangements are to be read counter-clockwise, so the following two are not equivalent since no rotation can bring one to the other.
1 1 4 3 3 4 2 2
There are (n – 1)! circular permutations of a set withn elements.
The cycles (including the fixed points) of a permutation of a set withn elements partition that set; so the lengths of these cycles form aninteger partition ofn, which is called thecycle type (or sometimescycle structure orcycle shape) of. There is a "1" in the cycle type for every fixed point of, a "2" for every transposition, and so on. The cycle type of is
This may also be written in a more compact form as[112231].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[41]
.
The number of cycle types of a set withn elements equals the value of thepartition function.
In general, composing permutations written in cycle notation follows no easily described pattern – the cycles of the composition can be different from those being composed. However the cycle type is preserved in the special case ofconjugating a permutation by another permutation, which means forming the product. Here, is theconjugate of by and its cycle notation can be obtained by taking the cycle notation for and applying to all the entries in it.[42] It follows that two permutations are conjugate exactly when they have the same cycle type.
The order of a permutation is the smallest positive integerm so that. It is theleast common multiple of the lengths of its cycles. For example, the order of is.
Every permutation of a finite set can be expressed as the product of transpositions.[43]Although many such expressions for a given permutation may exist, either they all contain an even number of transpositions or they all contain an odd number of transpositions. Thus all permutations can be classified aseven or odd depending on this number.
This result can be extended so as to assign asign, written, to each permutation. if is even and if is odd. Then for two permutations and
It follows that
The sign of a permutation is equal to the determinant of itspermutation matrix (below).
Apermutation matrix is ann ×n matrix that has exactly one entry 1 in each column and in each row, and all other entries are 0. There are several ways to assign a permutation matrix to a permutation of {1, 2, ...,n}. One natural approach is to define to be thelinear transformation of which permutes thestandard basis by, and define to be its matrix. That is, has itsjth column equal to the n × 1 column vector: its (i,j) entry is to 1 ifi =σ(j), and 0 otherwise. Since composition of linear mappings is described by matrix multiplication, it follows that this construction is compatible with composition of permutations:
.
For example, the one-line permutations have product, and the corresponding matrices are:
Composition of permutations corresponding to a multiplication of permutation matrices.
It is also common in the literature to find the inverse convention, where a permutationσ is associated to the matrix whose (i,j) entry is 1 ifj =σ(i) and is 0 otherwise. In this convention, permutation matrices multiply in the opposite order from permutations, that is,. In this correspondence, permutation matrices act on the right side of the standard row vectors:.
TheCayley table on the right shows these matrices for permutations of 3 elements.
In some applications, the elements of the set being permuted will be compared with each other. This requires that the setS has atotal order so that any two elements can be compared. The set {1, 2, ...,n} with the usual ≤ relation is the most frequently used set in these applications.
A number of properties of a permutation are directly related to the total ordering ofS, considering the permutation written in one-line notation as a sequence.
Anascent of a permutation σ ofn is any positioni < n where the following value is bigger than the current one. That is,i is an ascent if. For example, the permutation 3452167 has ascents (at positions) 1, 2, 5, and 6.
Similarly, adescent is a positioni < n with, so everyi with is either an ascent or a descent.
Anascending run of a permutation is a nonempty increasing contiguous subsequence 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). By contrast anincreasing subsequence of a permutation is not necessarily contiguous: it is an increasing sequence obtained by omitting some of the values of the one-line notation.For example, the permutation 2453167 has the ascending runs 245, 3, and 167, while it has an increasing subsequence 2367.
If a permutation hask − 1 descents, then it must be the union ofk ascending runs.[44]
The number of permutations ofn withk ascents is (by definition) theEulerian number; this is also the number of permutations ofn withk descents. Some authors however define the Eulerian number as the number of permutations withk ascending runs, which corresponds tok − 1 descents.[45]
An exceedance of a permutationσ1σ2...σn is an indexj such thatσj >j. If the inequality is not strict (that is,σj ≥j), thenj is called aweak exceedance. The number ofn-permutations withk exceedances coincides with the number ofn-permutations withk descents.[46]
Arecord orleft-to-right maximum of a permutationσ is an elementi such thatσ(j) <σ(i) for allj < i.
Foata'sfundamental bijection transforms a permutationσ with a given canonical cycle form into the permutation whose one-line notation has the same sequence of elements with parentheses removed.[27][47] For example:
Here the first element in each canonical cycle ofσ becomes a record (left-to-right maximum) of. Given, one may find its records and insert parentheses to construct the inverse transformation. Underlining the records in the above example:, which allows the reconstruction of the cycles ofσ.
The following table shows andσ for the six permutations ofS = {1, 2, 3}, with the bold text on each side showing the notation used in the bijection: one-line notation for and canonical cycle notation forσ.
As a first corollary, the number ofn-permutations with exactlyk records is equal to the number ofn-permutations with exactlyk cycles: this last number is the signlessStirling number of the first kind,. Furthermore, Foata's mapping takes ann-permutation withk weak exceedances to ann-permutation withk − 1 ascents.[47] For example, (2)(31) = 321 hask = 2 weak exceedances (at index 1 and 2), whereasf(321) = 231 hask − 1 = 1 ascent (at index 1; that is, from 2 to 3).
In the15 puzzle the goal is to get the squares in ascending order. Initial positions which have an odd number of inversions are impossible to solve.[48]
Aninversion of a permutation σ is a pair(i,j) of positions where the entries of a permutation are in the opposite order: and.[49] Thus a descent is an inversion at two adjacent positions. For example,σ = 23154 has (i,j) = (1, 3), (2, 3), and (4, 5), where (σ(i),σ(j)) = (2, 1), (3, 1), and (5, 4).
Sometimes an inversion is defined as the pair of values (σ(i),σ(j)); this makes no difference for thenumber of inversions, and the reverse pair (σ(j),σ(i)) is an inversion in the above sense for the inverse permutationσ−1.
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σ−1. To bring a permutation withk 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 ofk such operations. Moreover, any reasonable choice for the adjacent transpositions will work: it suffices to choose at each step a transposition ofi andi + 1 wherei 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). 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.Bubble sort andinsertion sort can be interpreted as particular instances of this procedure to put a sequence into order. 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. In fact, by enumerating all sequences of adjacent transpositions that would transformσ into the identity, one obtains (after reversal) acomplete list of all expressions of minimal length writingσ as a product of adjacent transpositions.
The number of permutations ofn withk inversions is expressed by aMahonian number.[50] This is the coefficient of in the expansion of the product
The notation denotes theq-factorial. This expansion commonly appears in the study ofnecklaces.
Let such that and.In this case, say the weight of the inversion is.Kobayashi (2011) proved the enumeration formula
One way to represent permutations ofn things is by an integerN 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). This gives the most compact representation of arbitrary permutations, and in computing is particularly attractive whenn is small enough thatN can be held in a machine word; for 32-bit words this meansn ≤ 12, and for 64-bit words this meansn ≤ 20. The conversion can be done via the intermediate form of a sequence of numbersdn,dn−1, ...,d2,d1, wheredi is a non-negative integer less thani (one may omitd1, as it is always 0, but its presence makes the subsequent conversion to a permutation easier to describe). The first step then is to simply expressN in thefactorial number system, which is just a particularmixed radix representation, where, for numbers less thann!, the bases (place values or multiplication factors) for successive digits are(n − 1)!,(n − 2)!, ..., 2!, 1!. The second step interprets this sequence as aLehmer code or (almost equivalently) as an inversion table.
Rothe diagram for
σi
i
1
2
3
4
5
6
7
8
9
Lehmer code
1
×
×
×
×
×
•
d9 = 5
2
×
×
•
d8 = 2
3
×
×
×
×
×
•
d7 = 5
4
•
d6 = 0
5
×
•
d5 = 1
6
×
×
×
•
d4 = 3
7
×
×
•
d3 = 2
8
•
d2 = 0
9
•
d1 = 0
Inversion table
3
6
1
2
4
0
2
0
0
In theLehmer code for a permutation σ, the numberdn represents the choice made for the first term σ1, the numberdn−1 represents the choice made for the second termσ2 among the remainingn − 1 elements of the set, and so forth. More precisely, eachdn+1−i gives the number ofremaining elements strictly less than the termσi. Since those remaining elements are bound to turn up as some later termσj, the digitdn+1−i counts theinversions (i,j) involvingi as smaller index (the number of valuesj for whichi < j andσi > σj). Theinversion table for σ is quite similar, but heredn+1−k counts the number of inversions (i,j) wherek = σj occurs as the smaller of the two values appearing in inverted order.[51]
Both encodings can be visualized by ann by nRothe diagram[52] (named afterHeinrich 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. 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.
To effectively convert a Lehmer codedn,dn−1, ...,d2,d1 into a permutation of an ordered setS, one can start with a list of the elements ofS in increasing order, and fori increasing from 1 ton setσi to the element in the list that is preceded bydn+1−i other ones, and remove that element from the list. To convert an inversion tabledn,dn−1, ...,d2,d1 into the corresponding permutation, one can traverse the numbers fromd1 todn while inserting the elements ofS from largest to smallest into an initially empty sequence; at the step using the numberd from the inversion table, the element fromS inserted into the sequence at the point where it is preceded byd elements already present. Alternatively one could process the numbers from the inversion table and the elements ofS both in the opposite order, starting with a row ofn empty slots, and at each step place the element fromS into the empty slot that is preceded byd other empty slots.
Converting successive natural numbers to the factorial number system produces those sequences inlexicographic 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 theplace of their entries 1 rather than by the value of their first entries). 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 thesignature of the permutation. 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. A permutation with Lehmer codedn,dn−1, ...,d2,d1 has an ascentn −i if and only ifdi ≥di+1.
In computing it may be required to generate permutations of a given sequence of values. 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. 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.
An obvious way to generate permutations ofn is to generate values for theLehmer code (possibly using thefactorial number system representation of integers up ton!), and convert those into the corresponding permutations. However, the latter step, while straightforward, is hard to implement efficiently, because it requiresn operations each of selection from a sequence and deletion from it, at an arbitrary position; of the obvious representations of the sequence as anarray or alinked list, both require (for different reasons) aboutn2/4 operations to perform the conversion. Withn 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. For this reason it does not seem useful, although certainly possible, to employ a specialdata structure that would allow performing the conversion from Lehmer code to permutation inO(n logn) time.
For generatingrandom permutations of a given sequence ofn values, it makes no difference whether one applies a randomly selected permutation ofn to the sequence, or chooses a random element from the set of distinct (multiset) permutations of the sequence. This is because, even though in case of repeated values there can be many distinct permutations ofn that result in the same permuted sequence, the number of such permutations is the same for each possible result. Unlike for systematic generation, which becomes unfeasible for largen due to the growth of the numbern!, there is no reason to assume thatn will be small for random generation.
The basic idea to generate a random permutation is to generate at random one of then! sequences of integersd1,d2,...,dn satisfying0 ≤di <i (sinced1 is always zero it may be omitted) and to convert it to a permutation through abijective correspondence. For the latter correspondence one could interpret the (reverse) sequence as a Lehmer code, and this gives a generation method first published in 1938 byRonald Fisher andFrank Yates.[53]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. This can be remedied by using a different bijective correspondence: after usingdi to select an element amongi remaining elements of the sequence (for decreasing values ofi), rather than removing the element and compacting the sequence by shifting down further elements one place, oneswaps the element with the final remaining element. 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. 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 immediateinduction. When the selected element happens to be the final remaining element, the swap operation can be omitted. 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.
The resulting algorithm for generating a random permutation ofa[0],a[1], ...,a[n − 1] can be described as follows inpseudocode:
forifromndownto 2dodi ← random element of { 0, ...,i − 1 }swapa[di] anda[i − 1]
This can be combined with the initialization of the arraya[i] =i as follows
forifrom 0ton−1dodi+1 ← random element of { 0, ...,i }a[i] ←a[di+1]a[di+1] ←i
Ifdi+1 =i, the first assignment will copy an uninitialized value, but the second will overwrite it with the correct valuei.
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.[54]
There are many ways to systematically generate all permutations of a given sequence.[55]One classic, simple, and flexible algorithm is based upon finding the next permutation inlexicographic ordering, if it exists. It can handle repeated values, for which case it generates each distinct multiset permutation once. Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using thefactorial number system) and converting those to permutations. 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. The method goes back toNarayana Pandita in 14th century India, and has been rediscovered frequently.[56]
The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
Find the largest indexk such thata[k] <a[k + 1]. If no such index exists, the permutation is the last permutation.
Find the largest indexl greater thank such thata[k] <a[l].
Swap the value ofa[k] with that ofa[l].
Reverse the sequence froma[k + 1] up to and including the final elementa[n].
For example, given the sequence [1, 2, 3, 4] (which is in increasing order), and given that the index iszero-based, the steps are as follows:
Indexk = 2, because 3 is placed at an index that satisfies condition of being the largest index that is still less thana[k + 1] which is 4.
Indexl = 3, because 4 is the only value in the sequence that is greater than 3 in order to satisfy the conditiona[k] <a[l].
The values ofa[2] anda[3] are swapped to form the new sequence [1, 2, 4, 3].
The sequence afterk-indexa[2] 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].
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 pointa[k] <a[k + 1] does not exist, indicating that this is the last permutation.
This method uses about 3 comparisons and 1.5 swaps per permutation, amortized over the whole sequence, not counting the initial sort.[57]
An alternative to the above algorithm, theSteinhaus–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. This ordering on the permutations was known to 17th-century English bell ringers, among whom it was known as "plain changes". 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. The same can also easily generate the subset of even permutations, again in constant time per permutation, by skipping every other output permutation.[56]
An alternative to Steinhaus–Johnson–Trotter isHeap's algorithm,[58] said byRobert Sedgewick in 1977 to be the fastest algorithm of generating permutations in applications.[55]
The following figure shows the output of all three aforementioned algorithms for generating all permutations of length, and of six additional algorithms described in the literature.
Ordering of all permutations of length generated by different algorithms. The permutations are color-coded, where 1, 2, 3, 4.[59]
Ehrlich's star-transposition algorithm:[56] in each step, the first entry of the permutation is exchanged with a later entry;
Zaks' prefix reversal algorithm:[60] in each step, a prefix of the current permutation is reversed to obtain the next permutation;
Sawada-Williams' algorithm:[61] each permutation differs from the previous one either by a cyclic left-shift by one position, or an exchange of the first two entries;
Corbett's algorithm:[62] each permutation differs from the previous one by a cyclic left-shift of some prefix by one position;
Single-track ordering:[63] each column is a cyclic shift of the other columns;
Single-trackGray code:[63] each column is a cyclic shift of the other columns, plus any two consecutive permutations differ only in one or two transpositions.
Nested swaps generating algorithm in steps connected to the nested subgroups. Each permutation is obtained from the previous by a transposition multiplication to the left. Algorithm is connected to theFactorial_number_system of the index.
Explicit sequence of swaps (transpositions, 2-cycles), is described here, each swap applied (on the left) to the previous chain providing a new permutation, such that all the permutations can be retrieved, each only once.[64] This counting/generating procedure has an additional structure (call it nested), as it is given in steps: after completely retrieving, continue retrieving by cosets of in, by appropriately choosing thecoset representatives to be described below. Since each is sequentially generated, there is alast element. So, after generating by swaps, the next permutation in has to be for some. Then all swaps that generated are repeated, generating the whole coset, reaching the last permutation in that coset; the next swap has to move the permutation to representative of another coset.
Continuing the same way, one gets coset representatives for the cosets of in; the ordered set () is called the set of coset beginnings. Two of these representatives are in the same coset if and only if, that is,. Concluding, permutations are all representatives of distinct cosetsif and only if for any, (no repeat condition). In particular, for all generated permutations to be distinct it is not necessary for the values to be distinct. In the process, one gets that and this provides the recursion procedure.
EXAMPLES: obviously, for one has; to build there are only two possibilities for the coset beginnings satisfying the no repeat condition; the choice leads to. To continue generating one needs appropriate coset beginnings (satisfying the no repeat condition): there is a convenient choice:, leading to. Then, to build a convenient choice for the coset beginnings (satisfying the no repeat condition) is, leading to.
From examples above one can inductively go to higher in a similar way, choosing coset beginnings of in, as follows: for even choosing all coset beginnings equal to 1 and for odd choosing coset beginnings equal to. With such choices the "last" permutation is for odd and for even (). Using these explicit formulae one can easily compute the permutation of certain index in the counting/generation steps with minimum computation. For this, writing the index in factorial base is useful. For example, the permutation for index is:, yelding finally,.
Because multiplying by swap permutation takes short computing time and every new generated permutation requires only one such swap multiplication, this generation procedure is quite efficient. Moreover as there is a simple formula, having the last permutation in each can save even more time to go directly to a permutation with certain index in fewer steps than expected as it can be done in blocks of subgroups rather than swap by swap.
Permutations are used in theinterleaver component of theerror detection and correction algorithms, such asturbo codes, for example3GPP Long Term Evolution mobile telecommunication standard uses these ideas (see 3GPP technical specification 36.212[65]).Such applications raise the question of fast generation of permutations satisfying certain desirable properties. One of the methods is based on thepermutation polynomials. Also as a base for optimal hashing in Unique Permutation Hashing.[66]
^1 is frequently used to represent theidentity element in a non-commutative group
^The order is often implicitly understood. A set of integers is naturally written from smallest to largest; a set of letters is written in lexicographic order. For other sets, a natural order needs to be specified explicitly.
^More precisely,variations without repetition. The term is still common in other languages and appears in modern English most often in translation.
^The natural order in this example is the order of the letters in the original word.
^In older textscircular permutation was sometimes used as a synonym forcyclic permutation, but this is no longer done. SeeCarmichael (1956, p. 7)
^Heath, Thomas Little (1981).A History of Greek Mathematics. New York: Dover Publications.ISBN0-486-24073-8.OCLC7703465.
^Broemeling, Lyle D. (1 November 2011). "An Account of Early Statistical Inference in Arab Cryptology".The American Statistician.65 (4):255–257.doi:10.1198/tas.2011.10191.S2CID123537702.
^Scheinerman, Edward A. (March 5, 2012)."Chapter 5: Functions".Mathematics: A Discrete Introduction (3rd ed.). Cengage Learning. p. 188.ISBN978-0840049421.Archived from the original on February 5, 2020. RetrievedFebruary 5, 2020.It is customary to use lowercase Greek letters (especially π, σ, and τ) to stand for permutations.
^Conway, John H.; Burgiel, Heidi; Goodman-Strauss, Chaim (2008).The Symmetries of Things. A K Peters. p. 179.A permutation---say, of the names of a number of people---can be thought of as moving either the names or the people. The alias viewpoint regards the permutation as assigning a new name oralias to each person (from the Latinalias = otherwise). Alternatively, from the alibi viewoint we move the people to the places corresponding to their new names (from the Latinalibi = in another place.)
^Bona 2012, p.87 [The book has a typo/error here, as it gives (45) instead of (54).]
^abStanley, Richard P. (2012).Enumerative Combinatorics: Volume I, Second Edition. Cambridge University Press. p. 30, Prop 1.3.1.ISBN978-1-107-01542-5.
^Kitaev, Sergey (2011).Patterns in Permutations and Words. Springer Science & Business Media. p. 119.ISBN978-3-642-17333-2.
^Biggs, Norman L.; White, A. T. (1979).Permutation groups and combinatorial structures. Cambridge University Press.ISBN978-0-521-22287-7.
^H. A. Rothe,Sammlung combinatorisch-analytischer Abhandlungen2 (Leipzig, 1800), 263–305. Cited inKnuth 1973, p. 14
^Fisher, R.A.; Yates, F. (1948) [1938].Statistical tables for biological, agricultural and medical research (3rd ed.). London: Oliver & Boyd. pp. 26–27.OCLC14222135.
^Bacher, A.; Bodini, O.; Hwang, H.K.; Tsai, T.H. (2017). "Generating Random Permutations by Coin Tossing: Classical Algorithms, New Analysis, and Modern Implementation" (ACM Trans. Algorithms 13(2): 24:1–24:43 ed.). pp. 24–43.
^Corbett, P. F. (1992). "Rotator graphs: An efficient topology for point-to-point multiprocessor networks".IEEE Transactions on Parallel and Distributed Systems.3 (5):622–626.doi:10.1109/71.159045.
Bona, Miklos (2012),Combinatorics of Permutations (2nd ed.), CRC Press,ISBN978-1-4398-5051-0
Brualdi, Richard A. (2010),Introductory Combinatorics (5th ed.), Prentice-Hall,ISBN978-0-13-602040-0
Cameron, Peter J. (1994),Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press,ISBN978-0-521-45761-3
Carmichael, Robert D. (1956) [1937],Introduction to the theory of Groups of Finite Order, Dover,ISBN978-0-486-60300-1{{citation}}:ISBN / Date incompatibility (help)
Knuth, Donald (1973),Sorting and Searching, The Art of Computer Programming, vol. 3 This book mentions the Lehmer code (without using that name) as a variantC1,...,Cn of inversion tables in exercise 5.1.1–7 (p. 19), together with two other variants.
Nering, Evar D. (1970),Linear Algebra and Matrix Theory (2nd ed.), New York:Wiley,LCCN76091646
Rotman, Joseph J. (2002),Advanced Modern Algebra, Prentice-Hall,ISBN978-0-13-087868-7
Stedman, Fabian (1677),Campanalogia, London The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for theSociety of College Youths, to which society the "Dedicatory" is addressed.In quotations the original long "S" has been replaced by a modern short "s".
Biggs, Norman L. (2002),Discrete Mathematics (2nd ed.), Oxford University Press,ISBN978-0-19-850717-8
Foata, Dominique; Schutzenberger, Marcel-Paul (1970),Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Mathematics, vol. 138, Berlin, Heidelberg: Springer-Verlag,ISBN978-3-540-04927-2. The link is to a freely available retyped (LaTeX'ed) and revised version of the text originally published by Springer-Verlag.
Knuth, Donald (1998),Sorting and Searching, The Art of Computer Programming, vol. 3 (Second ed.), Addison–Wesley,ISBN978-0-201-89685-5. Section 5.1: Combinatorial Properties of Permutations, pp. 11–72.
