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: SystemsDesign.Cloud

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 FisherYates Shuffle algorithm is to shuffle a deck of cards.
Algorithm:
The code below explains the algorithm. FisherYates 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 N^{th} 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 FisherYates shuffle technique, each of the 52! permutations of the deck will be equally likely.
Time Complexity:
FisherYates 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.
Follow Us On LinkedIn