Fisher–Yates Shuffle
Algorithm to perfectly shuffle a FINITE sequence, i.e., generating a random permutation of a finite sequence
-
Algorithms and Data Structures: TheAlgorist.com
-
System Design: DistributedComputing.dev
-
Low Level Design: LowLevelDesign.io
-
Frontend Engineering: FrontendEngineering.io
The Fisher–Yates shuffle is an algorithm for generating a random permutation of a finite sequence—in plain terms, the algorithm shuffles the sequence. The algorithm produces an unbiased permutation: every permutation is equally likely. It takes time proportional to the number of items being shuffled and shuffles them in place.
A real life application of Fisher-Yates Shuffle algorithm is to shuffle a deck of cards.
Algorithm:
The code below explains the algorithm. Fisher-Yates Shuffle can be implemented either recursively or iteratively as shown below:Recursive Approach:
Let's suppose we need to shuffle a sequence of elements with N items. Here is how the recursive approach works:- Shuffle the first (N - 1) items of the given sequence.
- Now, take the Nth element and randomly swap it with an element from the already shuffled first (N - 1) items.
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Iterative Approach:
Suppose, the given sequence has N elements, indexed from 0 to (N - 1). We iterate from 0 to (N - 1) and for each index i we generate a random index in the range [0, i] and if random index != i, then we swap the element at index i with the element at random index.
This is a Premium content.
Please subscribe to Algorithms course to access the code.
So, if you shuffle a card deck using Fisher-Yates shuffle technique, each of the 52! permutations of the deck will be equally likely.
Time Complexity:
Fisher-Yates Shuffle takes linear time. For shuffling a sequence of N elements, time complexity will be O(N). Note that Math.random() takes constant time in Java. It returns a random double in the range [0.0, 1.0).Related Chapter:
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
