TOPICS
Search

Random Permutation


A random permutation is a permutation containing a fixed number n of a random selection from a given set of elements. There are two main algorithms for constructing random permutations. The first constructs a vector of random real numbers and uses them as keys to records containing the integers 1 to n. The second starts with an arbitrary permutation and then exchanges the ith element with a randomly selected one from the first i elements for i=1, ..., n (Skiena 1990).

A random permutation on the integers {1,...,n} can be implemented in the Wolfram Language as RandomSample[Range[n]]. A random permutation in the permutation graph pg can be computed using RandomPermutation[pg], and n such random permutations by RandomPermutation[pg, n]. n random permutations in the symmetric group of order d can be computed using RandomPermutation[d, n].

There are an average of n(n-1)/4 permutation inversions in a permutation on n elements (Skiena 1990, p. 29). The expected number of permutation cycles of length 1 in a random permutation over the symmetric group S_d is 1.


See also

Permutation, Permutation Inversion

Explore with Wolfram|Alpha

References

Moses, L. E. and Oakford, R. V. Tables of Random Permutations. Stanford, CA: Stanford University Press, 1963.Skiena, S. "Random Permutations." §1.1.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 6-9 and 29, 1990.

Cite this as:

Weisstein, Eric W. "Random Permutation." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RandomPermutation.html

Subject classifications