perfect shuffle

(algorithm)

Definition: A permutation algorithm, or shuffle, that has exactly the same chance of producing any permutation.

Specialization (... is a kind of me.)
Fisher-Yates shuffle.

Note: Attaching random tags then sorting (see permutation) may not be a perfect shuffle: if tags may be duplicated, a stable sort has a greater chance of producing permutations with some items in the original order.

Author: PEB

Implementation

Discussion and explanation of what makes a shuffle perfect and two implementations (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 4 February 2005.
HTML page formatted Mon Sep 11 09:46:06 2006.

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