# Random permutation

__: Sequence where any order is equally likely__

**Short description**A **random permutation** is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and simulation. A good example of a random permutation is the shuffling of a deck of cards: this is ideally a random permutation of the 52 cards.

## Generating random permutations

### Entry-by-entry brute force method

One method of generating a random permutation of a set of size *n* uniformly at random (i.e., each of the *n*! permutations is equally likely to appear) is to generate a sequence by taking a random number between 1 and *n* sequentially, ensuring that there is no repetition, and interpreting this sequence (*x*_{1}, ..., *x*_{n}) as the permutation

- [math]\displaystyle{ \begin{pmatrix} 1 & 2 & 3 & \cdots & n \\ x_1 & x_2 & x_3 & \cdots & x_n \\ \end{pmatrix}, }[/math]

shown here in two-line notation.

This brute-force method will require occasional retries whenever the random number picked is a repeat of a number already selected. This can be avoided if, on the *i*th step (when *x*_{1}, ..., *x*_{i − 1} have already been chosen), one chooses a number *j* at random between 1 and *n* − *i* + 1 and sets *x*_{i} equal to the *j*th largest of the unchosen numbers.

### 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 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. It's easy to verify that any permutation of *n* elements will be produced by this algorithm with probability exactly 1/*n*!, thus yielding a uniform distribution over all such permutations.

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] */ } }

Note that if the `uniform()`

function is implemented simply as `random() % (m)`

then a bias in the results is introduced if the number of return values of `random()`

is not a multiple of m, but this becomes insignificant if the number of return values of `random()`

is orders of magnitude greater than m.

## Statistics on random permutations

### Fixed points

The probability distribution of the number of fixed points in a uniformly distributed random permutation approaches a Poisson distribution with expected value 1 as *n* grows. In particular, it is an elegant application of the inclusion–exclusion principle to show that the probability that there are no fixed points approaches 1/*e*. When *n* is big enough, the probability distribution of fixed points is almost the Poisson distribution with expected value 1.^{[1]} The first *n* moments of this distribution are exactly those of the Poisson distribution.

## Randomness testing

As with all random processes, the quality of the resulting distribution of an implementation of a randomized algorithm such as the Knuth shuffle (i.e., how close it is to the desired uniform distribution) depends on the quality of the underlying source of randomness, such as a pseudorandom number generator. There are many possible randomness tests for random permutations, such as some of the Diehard tests. A typical example of such a test is to take some permutation statistic for which the distribution is known and test whether the distribution of this statistic on a set of randomly generated permutations closely approximates the true distribution.

## See also

- Ewens's sampling formula — a connection with population genetics
- Faro shuffle
- Golomb–Dickman constant
- Random permutation statistics
- Shuffling algorithms — random sort method, iterative exchange method
- Pseudorandom permutation

## References

- ↑ Durstenfeld, Richard (1964-07-01). "Algorithm 235: Random permutation".
*Communications of the ACM***7**(7): 420. doi:10.1145/364520.364540. http://portal.acm.org/citation.cfm?doid=364520.364540.

## External links

- Random permutation at MathWorld
- 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

Original source: https://en.wikipedia.org/wiki/Random permutation.
Read more |