ideal random shuffle

(algorithm)

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

Generalization (I am a kind of ...)
randomized algorithm.

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

Note: Attaching random tags then sorting (see permutation) may not work: if tags may be duplicated, a deterministic sort will not randomly switch the order of elements with duplicate tags.

Author: PEB

Implementation

Discussion and explanation of what makes a shuffle ideal and two implementations (Haskell).

More information

Historical Note
Formerly called "perfect shuffle". Renamed in January 2009 when Dave Bayer pointed out that the term is almost universally used to mean dividing a list of elements (or deck of cards) exactly in half then precisely interleaving the two halves. This has been the use of "perfect shuffle" for decades.

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

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

Entry modified 4 October 2021.
HTML page formatted Mon Oct 4 14:22:58 2021.

Cite this as:
Paul E. Black, "ideal random shuffle", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 4 October 2021. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/idealRandomShuffle.html