Editing Permutation (section)

==Permutations in computing==
===Numbering permutations===
<!-- linked from redirect [[Rothe diagram]] -->
One way to represent permutations of ''n'' things is by an integer ''N'' with 0&nbsp;≤&nbsp;''N''&nbsp;&lt;&nbsp;''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 when ''n'' is small enough that ''N'' can be held in a machine word; for 32-bit words this means ''n''&nbsp;≤&nbsp;12, and for 64-bit words this means ''n''&nbsp;≤&nbsp;20. The conversion can be done via the intermediate form of a sequence of numbers ''d''<sub>''n''</sub>, ''d''<sub>''n''−1</sub>, ..., ''d''<sub>2</sub>, ''d''<sub>1</sub>, where ''d''<sub>''i''</sub> is a non-negative integer less than ''i'' (one may omit ''d''<sub>1</sub>, 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 express ''N'' in the ''[[factorial number system]]'', which is just a particular [[mixed radix]] representation, where, for numbers less than ''n''!, the bases (place values or multiplication factors) for successive digits are {{math|(''n'' − 1)!}}, {{math|(''n'' − 2)!}}, ..., 2!, 1!. The second step interprets this sequence as a [[Lehmer code]] or (almost equivalently) as an inversion table.

{| class="wikitable" style="float:right; text-align:center; margin: 1em"
|+ Rothe diagram for <math>\sigma = (6, 3, 8, 1, 4, 9, 7, 2, 5)</math>
|-
! {{diagonal split header|<sub>''i''</sub>| <sup>''σ''<sub>''i''</sub></sup>}}
! style="width:20pt;"| 1
! style="width:20pt;"| 2
! style="width:20pt;"| 3
! style="width:20pt;"| 4
! style="width:20pt;"| 5
! style="width:20pt;"| 6
! style="width:20pt;"| 7
! style="width:20pt;"| 8
! style="width:20pt;"| 9
! Lehmer code
|-
! 1
| × || × || × || × || × || • ||   ||   ||   || ''d''<sub>9</sub> = 5
|-
! 2
| × || × || • ||   ||   ||   ||   ||   ||   || ''d''<sub>8</sub> = 2
|-
! 3
| × || × ||   || × || × ||   || × || • ||   || ''d''<sub>7</sub> = 5
|-
! 4
| • ||   ||   ||   ||   ||   ||   ||   ||   || ''d''<sub>6</sub> = 0
|-
! 5
|   || × ||   || • ||   ||   ||   ||   ||   || ''d''<sub>5</sub> = 1
|-
! 6
|   || × ||   ||   || × ||   || × ||   || • || ''d''<sub>4</sub> = 3
|-
! 7
|   || × ||   ||   || × ||   || • ||   ||   || ''d''<sub>3</sub> = 2
|-
! 8
|   || • ||   ||   ||   ||   ||   ||   ||   || ''d''<sub>2</sub> = 0
|-
! 9
|   ||   ||   ||   || • ||   ||   ||   ||   || ''d''<sub>1</sub> = 0
|-
! Inversion table
| 3 || 6 || 1 || 2 || 4 || 0 || 2 || 0 || 0 ||
|}
In the '''Lehmer code''' for a permutation&nbsp;''σ'', the number ''d''<sub>''n''</sub> represents the choice made for the first term&nbsp;''σ''<sub>1</sub>, the number ''d''<sub>''n''−1</sub> represents the choice made for the second term
''σ''<sub>2</sub> among the remaining {{math|''n'' − 1}} elements of the set, and so forth. More precisely, each ''d''<sub>''n''+1−''i''</sub> gives the number of ''remaining'' elements strictly less than the term ''σ''<sub>''i''</sub>. Since those remaining elements are bound to turn up as some later term ''σ''<sub>''j''</sub>, the digit ''d''<sub>''n''+1−''i''</sub> counts the ''inversions'' (''i'',''j'') involving ''i'' as smaller index (the number of values ''j'' for which ''i''&nbsp;&lt;&nbsp;''j'' and ''σ''<sub>''i''</sub>&nbsp;&gt;&nbsp;''σ''<sub>''j''</sub>). The '''inversion table''' for&nbsp;''σ'' is quite similar, but here ''d''<sub>''n''+1−''k''</sub> counts the number of inversions (''i'',''j'') where ''k''&nbsp;=&nbsp;''σ''<sub>''j''</sub> occurs as the smaller of the two values appearing in inverted order.{{sfn|Knuth|1973|p=12}}

Both encodings can be visualized by an ''n''&nbsp;by&nbsp;''n'' '''Rothe diagram'''{{#tag:ref|[[Heinrich August Rothe|H. A. Rothe]], ''Sammlung combinatorisch-analytischer Abhandlungen'' '''2''' (Leipzig, 1800), 263–305. Cited in {{harvnb|Knuth|1973|p=14}}}} (named after [[Heinrich August Rothe]]) in which dots at (''i'',''σ''<sub>''i''</sub>) mark the entries of the permutation, and a cross at (''i'',''σ''<sub>''j''</sub>) marks the inversion (''i'',''j''); by the definition of inversions a cross appears in any square that comes both before the dot (''j'',''σ''<sub>''j''</sub>) in its column, and before the dot (''i'',''σ''<sub>''i''</sub>) 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''<sub>''n''</sub>, ''d''<sub>''n''−1</sub>, ..., ''d''<sub>2</sub>, ''d''<sub>1</sub> 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 ''σ''<sub>''i''</sub> to the element in the list that is preceded by ''d''<sub>''n''+1−''i''</sub> other ones, and remove that element from the list. To convert an inversion table ''d''<sub>''n''</sub>, ''d''<sub>''n''−1</sub>, ..., ''d''<sub>2</sub>, ''d''<sub>1</sub> into the corresponding permutation, one can traverse the numbers from ''d''<sub>1</sub> to ''d''<sub>''n''</sub> 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 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). 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 (permutation)|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''<sub>''n''</sub>, ''d''<sub>''n''−1</sub>, ..., ''d''<sub>2</sub>, ''d''<sub>1</sub> has an ascent {{math|''n'' − ''i''}} if and only if {{math|''d''<sub>''i''</sub> ≥ ''d''<sub>''i''+1</sub>}}.

===Algorithms to generate permutations===
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 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 data structure|array]] or a [[linked list]], both require (for different reasons) about ''n''<sup>2</sup>/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 [[big O notation|''O''(''n'' log ''n'')]] time.

====Random generation of permutations====
{{Main|Fisher–Yates shuffle}}
For generating [[random permutation]]s 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. 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. 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.

The basic idea to generate a random permutation is to generate at random one of the ''n''! sequences of integers ''d''<sub>1</sub>,''d''<sub>2</sub>,...,''d''<sub>''n''</sub> satisfying {{math|0 ≤ ''d''<sub>''i''</sub> &lt; ''i''}} (since ''d''<sub>1</sub> 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]].<ref>{{cite book
|author1=Fisher, R.A. |author2=Yates, F. | title = Statistical tables for biological, agricultural and medical research
| orig-year = 1938
| edition = 3rd
| year = 1948
| pages = 26–27
| publisher = Oliver & Boyd
| location = London
| oclc = 14222135
}}</ref>
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''<sub>''i''</sub> 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 [[swap (computer science)|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 (mathematics)|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 <code>''a''[0], ''a''[1], ..., ''a''[''n'' − 1]</code> can be described as follows in [[pseudocode]]:

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

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

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

If ''d''<sub>''i''+1</sub> = ''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.<ref>{{cite news|author1=Bacher, A. |author2=Bodini, O.|author3=Hwang, H.K.|author4=Tsai, T.H. | title = Generating Random Permutations by Coin Tossing: Classical Algorithms, New Analysis, and Modern Implementation.
| edition = ACM Trans. Algorithms 13(2): 24:1–24:43
| year = 2017
| pages = 24–43
}}</ref>

====Generation in lexicographic order====
There are many ways to systematically generate all permutations of a given sequence.<ref name=sedegewick1977>{{cite journal
|last=Sedgewick|first=R
|title=Permutation generation methods
|journal=Computing Surveys|year=1977|volume=9
|issue=2
|pages=137–164
|url=http://www.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf |archive-url=https://web.archive.org/web/20080221185652/http://www.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf |archive-date=2008-02-21 |url-status=live
|doi=10.1145/356689.356692
|s2cid=12139332
}}</ref>
One classic, simple, and flexible algorithm is based upon finding the next permutation in [[lexicographic 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 the [[factorial 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 to [[Narayana Pandit]]a in 14th century India, and has been rediscovered frequently.{{sfn|Knuth|2005|pp=1–26}}

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

# Find the largest index ''k'' such that {{math|''a''[''k''] < ''a''[''k'' + 1]}}.  If no such index exists, the permutation is the last permutation.
# Find the largest index ''l'' greater than ''k'' such that {{math|''a''[''k''] < ''a''[''l'']}}.
# Swap the value of ''a''[''k''] with that of ''a''[''l''].
# Reverse the sequence from ''a''[''k'' + 1] up to and including the final element ''a''[''n''].
For example, given the sequence [1, 2, 3, 4] (which is in increasing order), and given that the index is [[Zero-based numbering|zero-based]], the steps are as follows:
# 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.
# 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''].
# The values of ''a''[2] and ''a''[3] are swapped to form the new sequence [1, 2, 4, 3].
# The sequence after ''k''-index ''a''[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 point ''a''[''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.<ref>{{cite web|title=std::next_permutation|url=http://en.cppreference.com/w/cpp/algorithm/next_permutation|access-date=31 March 2018|work=cppreference.com|date=4 December 2017}}</ref>

====Generation with minimal changes====
{{main|Steinhaus–Johnson–Trotter algorithm|Heap's algorithm}}
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. 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.{{sfn|Knuth|2005|pp=1–26}}

An alternative to Steinhaus–Johnson–Trotter is [[Heap's algorithm]],<ref>{{cite journal|last=Heap|first=B. R.|title=Permutations by Interchanges|journal=The Computer Journal|year=1963|volume=6|issue=3|pages=293–298|doi=10.1093/comjnl/6.3.293|doi-access=free}}</ref> said by [[Robert Sedgewick (computer scientist)|Robert Sedgewick]] in 1977 to be the fastest algorithm of generating permutations in applications.<ref name=sedegewick1977/>

The following figure shows the output of all three aforementioned algorithms for generating all permutations of length <math>n=4</math>, and of six additional algorithms described in the literature.
[[File:Permutation generation algorithms10.svg|thumb|center|upright=2.2|Ordering of all permutations of length <math>n=4</math> generated by different algorithms. The permutations are color-coded, where {{legend-inline|red|1}}, {{legend-inline|yellow|2}}, {{legend-inline|green|3}}, {{legend-inline|blue|4}}.<ref>{{cite web|url=http://combos.org/perm|title=Generate permutations|last1=Mütze|first1=Torsten|last2=Sawada|first2=Joe|last3=Williams|first3=Aaron|website=Combinatorial Object Server|access-date=May 29, 2019}}</ref>]]

# Lexicographic ordering;
# [[Steinhaus–Johnson–Trotter algorithm]];
# [[Heap's algorithm]];
# Ehrlich's star-transposition algorithm:{{sfn|Knuth|2005|pp=1–26}} in each step, the first entry of the permutation is exchanged with a later entry;
# Zaks' prefix reversal algorithm:<ref name="Zaks_1984">{{cite journal|last=Zaks|first=S.|title=A new algorithm for generation of permutations|journal=[[BIT Numerical Mathematics]]|year=1984|volume=24|issue=2|pages=196–204|doi=10.1007/BF01937486|s2cid=30234652}}</ref> in each step, a prefix of the current permutation is reversed to obtain the next permutation;
# Sawada-Williams' algorithm:<ref>{{cite conference |title=A Hamilton path for the sigma-tau problem |last1=Sawada |first1=Joe |last2=Williams |first2=Aaron |date=2018 |publisher=[[Society for Industrial and Applied Mathematics]] (SIAM) | book-title=Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |pages=568–575 |location=New Orleans, Louisiana |doi=10.1137/1.9781611975031.37|doi-access=free }}</ref> 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:<ref name="Corbett_1992">{{cite journal|last=Corbett|first=P. F.|title=Rotator graphs: An efficient topology for point-to-point multiprocessor networks|journal=IEEE Transactions on Parallel and Distributed Systems|year=1992|volume=3|issue=5|pages=622–626|doi=10.1109/71.159045}}</ref> each permutation differs from the previous one by a cyclic left-shift of some prefix by one position;
# Single-track ordering:<ref name="Arndt_2011">{{cite book |author-last=Arndt |author-first=Jörg|title=Matters Computational. Ideas, Algorithms, Source Code| date=2011| publisher=[[Springer Science+Business Media|Springer]]| doi=10.1007/978-3-642-14764-7|isbn=978-3-642-14763-0}}</ref> each column is a cyclic shift of the other columns;
# Single-track Gray code:<ref name="Arndt_2011"/> 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 <math>S_k\subset S_{k+1}</math>. 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.

====Generation of permutations in nested swap steps====
Explicit sequence of swaps (transpositions, 2-cycles <math>(pq)</math>), 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.<ref>{{cite book
|author1=Popp, O.T. | title = Quickly Handling Big Permutations
| orig-year = 
| edition = 
| year = 2002
| pages = 
| publisher = priv. comm.
| location = 
| oclc = 
}}</ref> This counting/generating procedure has an additional structure (call it nested), as it is given in steps: after completely retrieving <math>S_{k-1}</math>, continue retrieving <math>S_{k}\backslash S_{k-1}</math> by cosets <math>S_{k-1}\tau_i</math> of <math>S_{k-1}</math> in <math>S_k</math>,  by appropriately choosing the coset representatives <math>\tau_i</math> to be described below. Since each <math>S_m</math> is sequentially generated, there is a ''last element'' <math>\lambda_m\in S_m</math>. So, after generating <math>S_{k-1}</math> by swaps, the next permutation in <math>S_{k}\backslash S_{k-1}</math>  has to be <math>\tau_1=(p_1k)\lambda_{k-1}</math> for some <math>1\leq p_1<k</math>. Then all swaps that generated  <math>S_{k-1}</math> are repeated, generating the whole coset <math>S_{k-1}\tau_1</math>, reaching the last permutation in that coset <math>\lambda_{k-1}\tau_1</math>; the next swap has to move the permutation to representative of another coset <math>\tau_2=(p_2k)\lambda_{k-1}\tau_1</math>. 

Continuing the same way, one gets coset representatives <math>\tau_j=(p_{j}k)\lambda_{k-1}\cdots \lambda_{k-1}(p_{i}k)\lambda_{k-1}\cdots\lambda_{k-1}(p_{1}k)\lambda_{k-1}</math> for the cosets of  <math>S_{k-1}</math> in <math>S_k</math>; the ordered set <math>(p_1,\ldots , p_{k-1})</math> (<math>0\leq p_i<k</math>) is called the set of coset beginnings. Two of these representatives are in the same coset if and only if  <math>\tau_j(\tau_i)^{-1}=(p_{j}k)\lambda_{k-1}(p_{j-1}k)\lambda_{k-1}\cdots \lambda_{k-1}(p_{i+1}k)=\varkappa_{ij}\in S_{k-1}</math>, that is,  <math>\varkappa_{ij} (k)=k</math>. Concluding, permutations <math>\tau_i\in S_k-S_{k-1}</math> are all representatives of distinct cosets if and only if for any <math>k>j>i\geq 1</math>, <math>(\lambda_{k-1})^{j-i}p_{i}\neq p_j</math> (no repeat condition).  In particular, for all generated permutations to be distinct it is not necessary for the <math>p_i</math> values to be distinct. In the process, one gets that <math>\lambda_k=\lambda_{k-1}(p_{k-1}k)\lambda_{k-1}(p_{k-2}k)\lambda_{k-1}\cdots\lambda_{k-1}(p_{1}k)\lambda_{k-1}</math> and this provides the recursion procedure. 

EXAMPLES: obviously, for <math>\lambda_2</math> one has <math>\lambda_2=(12)</math>; to build <math>\lambda_3</math> there are only two possibilities for the coset beginnings satisfying the no repeat condition; the choice <math> p_1=p_2=1</math> leads to <math>\lambda_3=\lambda_2(13)\lambda_2(13)\lambda_2=(13)</math>. To continue generating <math>S_4</math> one needs appropriate  coset beginnings (satisfying the no repeat condition): there is a convenient choice: <math>p_1=1, p_2=2, p_3=3</math>, leading to  <math>\lambda_4=(13)(1234)(13)=(1432)</math>. Then, to build <math>\lambda_5</math> a convenient choice for the coset beginnings (satisfying the no repeat condition) is <math> p_1=p_2=p_3=p_4=1</math>, leading to <math>\lambda_5=(15)</math>. 

From examples above one can inductively go to higher <math>k</math> in a similar way, choosing coset beginnings of <math>S_{k}</math> in  <math>S_{k+1}</math>, as follows: for <math>k</math> even choosing all coset beginnings equal to 1 and for <math>k</math> odd choosing coset beginnings equal to <math>(1, 2,\dots , k)</math>. With such choices the "last" permutation is <math>\lambda_k=(1k)</math> for <math>k</math> odd and  <math>\lambda_k=(1k_-)(12\cdots k)(1k_-)</math> for <math>k</math> even (<math>k_-=k-1</math>). 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 <math>699=5(5!)+4(4!)+1(2!)+1(1!)</math> is: <math>\sigma=\lambda_2(13)\lambda_2(15)\lambda_4(15)\lambda_4(15)\lambda_4(15)\lambda_4(56)\lambda_5(46)\lambda_5(36)\lambda_5(26)\lambda_5(16)\lambda_5=</math> <math>\lambda_2(13)\lambda_2((15)\lambda_4)^4(\lambda_5)^{-1}\lambda_6=(23)(14325)^{-1}(15)(15)(123456)(15)=</math><math>(23)(15234)(123456)(15)</math>, yelding finally, <math>\sigma=(1653)(24)</math>.

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 <math>S_k</math>  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.

===Applications===
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<ref>{{cite web| url = http://www.3gpp.org/ftp/Specs/html-info/36212.htm| title = 3GPP TS 36.212}}</ref>).
Such applications raise the question of fast generation of permutations satisfying certain desirable properties. One of the methods is based on the [[permutation polynomials]]. Also as a base for optimal hashing in Unique Permutation Hashing.<ref>{{cite journal |first1=Shlomi |last1=Dolev |first2=Limor |last2=Lahiani |first3=Yinnon |last3=Haviv |title=Unique permutation hashing |journal=Theoretical Computer Science |volume=475 |year=2013 |pages=59–65 |doi=10.1016/j.tcs.2012.12.047 |doi-access=free }}</ref>