Random permutation


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 length n uniformly at random 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 as the permutation
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 ith step, one chooses a number j at random between 1 and n − i + 1 and sets xi equal to the jth 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, and then go through the positions 0 through n − 2, and for each position i swap the element currently there with a randomly chosen element from positions i through n − 1, 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; /* Returns a random integer 0 <= uniform <= m-1 with uniform distribution */
void initialize_and_permute

Note that if the uniform function is implemented simply as random % 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. 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 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.