permutation

(algorithm)

Definition: A rearrangement of elements, where none are lost, added, or changed. The Fisher-Yates shuffle randomly permutes elements.

Also known as shuffle.

Generalization (I am a kind of ...)
combination.

Specialization (... is a kind of me.)
ideal random shuffle, Fisher-Yates shuffle, Johnson-Trotter, sort, derangement.

Aggregate parent (I am a part of or used in ...)
American flag sort.

See also pseudo-random number generator.

Note: A sort is a permutation where the items are arranged in some order. A derangement is a permutation where no item is in its original position.

There are n! permutations of n (distinguishable) elements.

Author: PEB

Implementation

The (Combinatorial) Object Server's information on Permutations (Pascal and C); Michael Gilleland's PermutationGenerator class (Java); (Pascal, Fortran, Mathematica, and C); (Fortran). Perfect shuffle (Haskell).

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 9 January 2009.
HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:
Paul E. Black, "permutation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 9 January 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/permutation.html