Editing Permutation (section)

====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>