Random permutation

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 fields include 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.

One method of generating a random permutation of a set of length "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

: egin{pmatrix}1 & 2 & 3 & cdots & n \x_1 & x_2 & x_3 & cdots & x_n \end{pmatrix}.

The above brute-force method will require occasional retries whenever the random number picked is a repeat of a number already selected. A simple algorithm to generate a permutation of "n" items uniformly at random without retries, known as the Knuth shuffle, is to start with the identity permutation or any other permutation, and then go through the positions 1 through "n"−1, and for each position "i" swap the element currently there with an arbitrarily chosen element from positions "i" through "n", 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.

For an account of the probability distribution of the number of fixed points of a uniformly distributed random permutation, see rencontres numbers. That distribution 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". The first "n" moments of this distribution are exactly those of the Poisson distribution.

See Ewens's sampling formula for a connection with population genetics.

See also

* Golomb–Dickman constant
* Perfect shuffle
* Random permutation statistics
* Shuffling algorithms — random sort method, iterative exchange method

External links

* [http://mathworld.wolfram.com/RandomPermutation.html Random permutation] at MathWorld
* [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

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Random permutation statistics — The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example,… …   Wikipedia

  • Permutation — For other uses, see Permutation (disambiguation). The 6 permutations of 3 balls In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values.… …   Wikipedia

  • Permutation cipher — In classical cryptography, a permutation cipher is a transposition cipher in which the key is a permutation.To apply a cipher, a random permutation of size e is generated (the larger the value of e the more secure the cipher). The plaintext is… …   Wikipedia

  • Random function — A random function is a function chosen at random from a finite family of functions. Typically, the family consists of the set of all maps from the domain to the image set. Thus, a random function can be considered to map each input independently… …   Wikipedia

  • Permutation box — In cryptography, a permutation box (or P box) is a method of bit shuffling used to permute or transpose bits across S boxes inputs, retaining diffusion while transposing.[1] In block ciphers, the S boxes and P Boxes are used to make the relation… …   Wikipedia

  • List of permutation topics — This is a list of topics on mathematical permutations.*Alternating group *Alternating permutation *Bijection *Circular shift *Combination *Cycle index *Cycle notation *Cyclic order *Cyclic permutation *Derangement *Even and odd permutations… …   Wikipedia

  • Pseudorandom permutation — In cryptography, a pseudorandom permutation, abbreviated PRP, is an idealized block cipher. It means the cipher that cannot be distinguished from a random permutation (that is, a permutation selected at random with uniform probability, from the… …   Wikipedia

  • Exchangeable random variables — An exchangeable sequence of random variables is asequence X 1, X 2, X 3, ... of random variables such that for any finite permutation sigma; of the indices 1, 2, 3, ..., i.e. any permutation sigma; that leaves all but finitely many indices fixed …   Wikipedia

  • Capablanca random chess — Chess diagram 8x10|= tright = 8 |nd|bd|nd|cd|qd|rd|bd|ad|kd|rd|= 7 |pd|pd|pd|pd|pd|pd|pd|pd|pd|pd|= 6 | | | | | | | | | | |= 5 | | | | | | | | | | |= 4 | | | | | | | | | | |= 3 | | | | | | | | | | |= 2 |pl|pl|pl|pl|pl|pl|pl|pl|pl|pl|= 1… …   Wikipedia

  • Claw-free permutation — In mathematical and computer science field of cryptography, a group of three numbers (x,y,z) is said to be a claw of two permutations f0 and f1 if f0(x) = f1(y) = z. A pair of permutations f0 and f1 are said to be claw free if there is no… …   Wikipedia