Editing Random permutation

{{Short description|Sequence where any order is equally likely}}
{{refimprove|date=May 2024}}
A '''random permutation''' is a [[sequence]] where any order of its items is equally likely at [[random]], that is, it is a [[permutation]]-valued [[random variable]] of a set of objects. The use of random permutations is common in [[Game of chance|games of chance]] and in [[randomized algorithm]]s in [[coding theory]], [[cryptography]], and [[simulation]]. A good example of a random permutation is the fair [[shuffling]] of a standard [[Playing card|deck of cards]]:  this is ideally a random permutation of the 52 cards.

==Computation of random permutations==
===Entry-by-entry methods===
One algorithm for generating a random permutation of a set of size ''n'' [[uniform distribution (discrete)|uniformly at random]], i.e., such that each of the ''n''! [[permutation]]s is equally likely to appear, is to generate a [[sequence]] by uniformly randomly selecting an integer between 1 and ''n'' (inclusive), sequentially and without replacement ''n'' times, and then to interpret this sequence (''x''<sub>1</sub>, ..., ''x''<sub>''n''</sub>) as the permutation

: <math>\begin{pmatrix}
1 & 2 & 3 & \cdots & n \\
x_1 & x_2 & x_3 & \cdots & x_n \\
\end{pmatrix},</math>

shown here in [[permutation#Cycle notation|two-line notation]].

An inefficient brute-force method for sampling without replacement could select from the numbers between 1 and ''n'' at every step, retrying the selection whenever the random number picked is a repeat of a number already selected until selecting a number that has not yet been selected. The expected number of retries per step in such cases will scale with the inverse of the fraction of numbers already selected, and the overall number of retries as the sum of those inverses, making this an inefficient approach. 

Such retries can be avoided using an algorithm where, on each ''i''th step when ''x''<sub>1</sub>, ..., ''x''<sub>''i'' &minus; 1</sub> have already been chosen, one chooses a uniformly random number ''j'' from between 1 and ''n'' &minus; ''i'' + 1 (inclusive) and sets ''x''<sub>''i''</sub> equal to the ''j''th largest of the numbers that have not yet been selected. This selects uniformly randomly among the remaining numbers at every step without retries.

===Fisher-Yates shuffles===
A simple [[algorithm]] to generate a permutation of ''n'' items uniformly at random without retries, known as the [[Fisher–Yates shuffle]], is to start with any permutation (for example, the [[Identity function|identity permutation]]), and then go through the positions 0 through ''n'' − 2 (we use a convention where the first element has index 0, and the last element has index ''n'' − 1), and for each position ''i'' '''swap''' the element currently there with a randomly chosen element from positions ''i'' through ''n'' − 1 (the end), inclusive. Any permutation of ''n'' elements will be produced by this algorithm with probability exactly 1/''n''!, thus yielding a uniform distribution of the permutations.

<syntaxhighlight lang="c">
unsigned uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m-1 with uniform distribution */

void initialize_and_permute(unsigned permutation[], unsigned n)
{
    unsigned i;
    for (i = 0; i <= n-2; i++) {
        unsigned j = i+uniform(n-i); /* A random integer such that i ≤ j < n */
        swap(permutation[i], permutation[j]);   /* Swap the randomly picked element with permutation[i] */
    }
}
</syntaxhighlight>

If the <code>uniform()</code> function is implemented simply as <code>random() % (m)</code> then there will be a bias in the distribution of permutations if the number of return values of <code>random()</code> is not a multiple of m. However, this effect is small if the number of return values of <code>random()</code> is orders of magnitude greater than m.

=== Randomness testing ===
As with all computational implementations of random processes, the quality of the distribution generated by an implementation of a randomized algorithm such as the Fisher-Yates shuffle, i.e., how close the actually generated distribution is to the desired distribution, will depend on the quality of underlying sources of randomness in the implementation such as [[pseudorandom number generator|pseudorandom number generators]] or [[Hardware random number generator|hardware random number generators]]. There are many [[randomness test]]s for random permutations, such as the "overlapping permutations" test of the [[Diehard tests]]. A typical form of such tests is to take some [[Random permutation statistics|permutation statistic]] for which the distribution is theoretically known and then test whether the distribution of that statistic on a set of randomly generated permutations from an implementation closely approximates the distribution of that statistic from the true distribution.

==Statistics on random permutations==
{{main|Random permutation statistics}}
===Fixed points===
{{main|Rencontres numbers}}
The [[probability distribution]] for the number of [[Fixed point (mathematics)|fixed points]] of a uniformly distributed random permutation of ''n'' elements approaches a [[Poisson distribution]] with [[expected value]] 1 as ''n'' grows.<ref>{{Cite journal |last=Durstenfeld |first=Richard |date=1964-07-01 |title=Algorithm 235: Random permutation |journal=Communications of the ACM |volume=7 |issue=7 |pages=420 |doi=10.1145/364520.364540 |doi-access=free}}</ref> The first ''n'' [[moment (mathematics)|moments]] of this distribution are exactly those of the Poisson distribution. In particular, the probability that a random permutation has no fixed points (i.e., that the permutation is a [[derangement]]) approaches 1/''e'' as ''n'' increases.

== See also ==
* [[Ewens's sampling formula]] — a connection with [[population genetics]]
* [[Faro shuffle]]
* [[Golomb–Dickman constant]]
* [[Random permutation statistics]]
* [[Shuffle#Shuffling algorithms|Shuffling algorithms]] — random sort method, iterative exchange method
* [[Pseudorandom permutation]]

==References==
{{Reflist}}

== External links ==
* [http://mathworld.wolfram.com/RandomPermutation.html Random permutation] at [[MathWorld]]
* [https://web.archive.org/web/20180619075139/http://www.techuser.net/randpermgen.html Random permutation generation] -- detailed and practical explanation of Knuth shuffle algorithm and its variants for generating ''k''-permutations (permutations of ''k'' elements chosen from a list) and ''k''-subsets (generating a subset of the elements in the list without replacement) with pseudocode

[[Category:Permutations]]
[[Category:Randomized algorithms]]