Permutation

 ( Arab Inventions ) 

The example above would then be:

$\backslash sigma\; =\; \backslash begin\{pmatrix\}$

 1 & 2 & 3 & 4 & 5 & 6 \\
 2 & 6 & 5 & 4 & 3 & 1
     

\end{pmatrix} = 2 6 5 4 3 1.

This compact form is common in elementary combinatorics and computer science. It is especially useful in applications where the permutations are to be compared as larger or smaller using lexicographic order.

To write down the permutation $\backslash sigma$ in cycle notation, one proceeds as follows:

1. Write an opening bracket followed by an arbitrary element x of $S$: $(\backslash ,x$
2. Trace the orbit of x, writing down the values under successive applications of $\backslash sigma$: $(\backslash ,x,\backslash sigma(x),\backslash sigma(\backslash sigma(x)),\backslash ldots$
3. Repeat until the value returns to x, and close the parenthesis without repeating x: $(\backslash ,x\backslash ,\backslash sigma(x)\backslash ,\backslash sigma(\backslash sigma(x))\backslash ,\backslash ldots\backslash ,)$
4. Continue with an element y of S which was not yet written, and repeat the above process: $(\backslash ,x\backslash ,\backslash sigma(x)\backslash ,\backslash sigma(\backslash sigma(x))\backslash ,\backslash ldots\backslash ,)(\backslash ,y\backslash ,\backslash ldots\backslash ,)$
5. Repeat until all elements of S are written in cycles.

Also, it is common to omit 1-cycles, since these can be inferred: for any element x in S not appearing in any cycle, one implicitly assumes $\backslash sigma(x)\; =\; x$.

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 (a cyclic 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 $\backslash sigma\; =\; 2\; 6\; 5\; 4\; 3\; 1$ can be written in cycle notation as: $$\backslash sigma\; =\; (126)(35)(4)\; =\; (126)(35).$$ This may be seen as the composition $\backslash sigma\; =\; \backslash kappa\_1\; \backslash kappa\_2$ of cyclic permutations $$\backslash kappa\_1\; =\; (126)\; =\; (126)(3)(4)(5),\backslash quad\; \backslash kappa\_2\; =\; (35)=\; (35)(1)(2)(4)(6).$$ While permutations in general do not commute, disjoint cycles do; for example: $$\backslash sigma\; =\; (126)(35)\; =\; (35)(126).$$ Also, each cycle can be rewritten from a different starting point; for example, $$\backslash sigma\; =\; (126)(35)\; =\; (261)(53).$$ 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, $$\backslash sigma^\{-1\}\; =\; \backslash left(\backslash vphantom\{A^2\}(126)(35)\backslash right)^\{-1\}\; =\; (621)(53).$$

• in each cycle the largest element is listed first
• the cycles are sorted in increasing order of their first element, not omitting 1-cycles

For example, $$(513)(6)(827)(94)$$ is a permutation of $S\; =\; \backslash \{1,\; 2,\; \backslash ldots\; ,\; 9\backslash \}$ in canonical cycle notation. The

Richard Stanley calls this the "standard representation" of a permutation,

Here the first element in each canonical cycle of becomes a record (left-to-right maximum) of $\backslash hat\backslash sigma$. Given $\backslash hat\backslash sigma$, one may find its records and insert parentheses to construct the inverse transformation $\backslash sigma=f^\{-1\}(\backslash hat\backslash sigma)$. Underlining the records in the above example: $\backslash hat\backslash sigma\; =\; \backslash underline\{5\}\backslash ,\; 1\backslash ,\; 3\backslash ,\; \backslash underline\{6\}\backslash ,\; \backslash underline\{8\}\backslash ,2\backslash ,7\backslash ,\backslash underline\{9\}\backslash ,4$, which allows the reconstruction of the cycles of .

The following table shows $\backslash hat\backslash sigma$ and for the six permutations of S = {1, 2, 3}, with the bold text on each side showing the notation used in the bijection: one-line notation for $\backslash hat\backslash sigma$ and canonical cycle notation for .

As a first corollary, the number of n-permutations with exactly k records is equal to the number of n-permutations with exactly k cycles: this last number is the signless Stirling number of the first kind, $c(n,\; k)$. Furthermore, Foata's mapping takes an n-permutation with k weak exceedances to an n-permutation with ascents. For example, (2)(31) = 321 has k = 2 weak exceedances (at index 1 and 2), whereas has ascent (at index 1; that is, from 2 to 3).

Sometimes an inversion is defined as the pair of values ( σ( i), σ( j)); this makes no difference for the number of inversions, and the reverse pair ( σ( j), σ( i)) is an inversion in the above sense for the inverse permutation σ⁻¹.

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 σ⁻¹. 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. Moreover, any reasonable choice for the adjacent transpositions will work: it suffices to choose at each step a transposition of i and 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). 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 and insertion 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) a complete list of all expressions of minimal length writing σ as a product of adjacent transpositions.

The number of permutations of n with k inversions is expressed by a Mahonian number. This is the coefficient of $q^k$ in the expansion of the product

$$n\_q!\; =\; \backslash prod\_\{m=1\}^n\backslash sum\_\{i=0\}^\{m-1\}q^i\; =\; 1\; \backslash left(1\; +\; q\backslash right)\backslash left(1\; +\; q\; +\; q^2\backslash right)\; \backslash cdots\; \backslash left(1\; +\; q\; +\; q^2\; +\; \backslash cdots\; +\; q^\{n-1\}\backslash right),$$

The notation $n\_q!$ denotes the q-factorial. This expansion commonly appears in the study of necklaces.

Let $\backslash sigma\; \backslash in\; S\_n,\; i,\; j\backslash in\; \backslash \{1,\; 2,\; \backslash dots,\; n\backslash \}$ such that

where $\backslash le$ denotes Bruhat order in the . This graded partial order often appears in the context of .

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. 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 code d _n, d _n−1, ..., d₂, d₁ 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 d _{n+1− i} other ones, and remove that element from the list. To convert an inversion table d _n, d _n−1, ..., d₂, d₁ into the corresponding permutation, one can traverse the numbers from d₁ to d _n 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. 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.

Converting successive 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). 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. 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 code d _n, d _n−1, ..., d₂, d₁ has an ascent if and only if .

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!), and convert those into the corresponding permutations. 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. 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. 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.

The basic idea to generate a random permutation is to generate at random one of the n! sequences of integers d₁, d₂,..., d _n satisfying (since d₁ is always zero it may be omitted) and to convert it to a permutation through a bijective 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 by Ronald Fisher and Frank Yates. 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 using d _i 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. 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 immediate induction. 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 of ''a''[0], ''a''[1], ..., ''a''[''n'' − 1] can be described as follows in pseudocode:

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

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

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

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

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.

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the largest index k such that . If no such index exists, the permutation is the last permutation.
2. Find the largest index l greater than k such that .
3. Swap the value of a k with that of al.
4. Reverse the sequence from a k up to and including the final element an.

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 which is 4.
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 < al.
3. The values of a2 and a3 are swapped to form the new sequence 1,.
4. The sequence after k-index a2 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,.

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

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.

The following figure shows the output of all three aforementioned algorithms for generating all permutations of length $n=4$, and of six additional algorithms described in the literature.

1. Lexicographic ordering;
2. Steinhaus–Johnson–Trotter algorithm;
3. Heap's algorithm;
4. Ehrlich's star-transposition algorithm: in each step, the first entry of the permutation is exchanged with a later entry;
5. Zaks' prefix reversal algorithm: in each step, a prefix of the current permutation is reversed to obtain the next permutation;
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;
7. Corbett's algorithm: each permutation differs from the previous one by a cyclic left-shift of some prefix by one position;
8. Single-track ordering:
   (2026). 9783642147630, Springer. ISBN 9783642147630
   each column is a cyclic shift of the other columns;
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.
10. Nested swaps generating algorithm in steps connected to the nested subgroups $S\_k\backslash subset\; S\_\{k+1\}$. Each permutation is obtained from the previous by a transposition multiplication to the left. Algorithm is connected to the Factorial number system of the index.

Continuing the same way, one gets coset representatives $\backslash tau\_j=(p\_\{j\}k)\backslash lambda\_\{k-1\}\backslash cdots\; \backslash lambda\_\{k-1\}(p\_\{i\}k)\backslash lambda\_\{k-1\}\backslash cdots\backslash lambda\_\{k-1\}(p\_\{1\}k)\backslash lambda\_\{k-1\}$ for the cosets of $S\_\{k-1\}$ in $S\_k$; the ordered set $(p\_1,\backslash ldots\; ,\; p\_\{k-1\})$ (

EXAMPLES: obviously, for $\backslash lambda\_2$ one has $\backslash lambda\_2=(12)$; to build $\backslash lambda\_3$ there are only two possibilities for the coset beginnings satisfying the no repeat condition; the choice $p\_1=p\_2=1$ leads to $\backslash lambda\_3=\backslash lambda\_2(13)\backslash lambda\_2(13)\backslash lambda\_2=(13)$. To continue generating $S\_4$ one needs appropriate coset beginnings (satisfying the no repeat condition): there is a convenient choice: $p\_1=1,\; p\_2=2,\; p\_3=3$, leading to $\backslash lambda\_4=(13)(1234)(13)=(1432)$. Then, to build $\backslash lambda\_5$ a convenient choice for the coset beginnings (satisfying the no repeat condition) is $p\_1=p\_2=p\_3=p\_4=1$, leading to $\backslash lambda\_5=(15)$.

From examples above one can inductively go to higher $k$ in a similar way, choosing coset beginnings of $S\_\{k\}$ in $S\_\{k+1\}$, as follows: for $k$ even choosing all coset beginnings equal to 1 and for $k$ odd choosing coset beginnings equal to $(1,\; 2,\backslash dots\; ,\; k)$. With such choices the "last" permutation is $\backslash lambda\_k=(1k)$ for $k$ odd and $\backslash lambda\_k=(1k\_-)(12\backslash cdots\; k)(1k\_-)$ for $k$ even ($k\_-=k-1$). 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 $699=5(5!)+4(4!)+1(2!)+1(1!)$ is: $\backslash sigma=\backslash lambda\_2(13)\backslash lambda\_2(15)\backslash lambda\_4(15)\backslash lambda\_4(15)\backslash lambda\_4(15)\backslash lambda\_4(56)\backslash lambda\_5(46)\backslash lambda\_5(36)\backslash lambda\_5(26)\backslash lambda\_5(16)\backslash lambda\_5=$ $\backslash lambda\_2(13)\backslash lambda\_2((15)\backslash lambda\_4)^4(\backslash lambda\_5)^\{-1\}\backslash lambda\_6=(23)(14325)^\{-1\}(15)(15)(123456)(15)=$$(23)(15234)(123456)(15)$, yelding finally, $\backslash sigma=(1653)(24)$.

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 $S\_k$ 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.

• Alternating permutation
• Convolution
• Cyclic order
• Even and odd permutations
• Josephus permutation
• Levi-Civita symbol
• List of permutation topics
• Major index
• Permutation category
• Permutation group
• Permutation pattern
• Permutation representation (symmetric group)
• Probability
• Rencontres numbers
• Sorting network
• Substitution cipher
• Superpattern
• Superpermutation
• Twelvefold way
• Weak order of permutations

• This book mentions the Lehmer code (without using that name) as a variant C₁,..., C _n of inversion tables in exercise 5.1.1–7 (p. 19), together with two other variants.
• Fascicle 2, first printing.
• The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Society of College Youths, to which society the "Dedicatory" is addressed. In quotations the original long "S" has been replaced by a modern short "s".

• . The link is to a freely available retyped (LaTeX'ed) and revised version of the text originally published by Springer-Verlag.
• . Section 5.1: Combinatorial Properties of Permutations, pp. 11–72.