Fisher–Yates Shuffle
Algorithm to perfectly shuffle a FINITE sequence, i.e., generating a random permutation of a finite sequence

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
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 access the code.
After subscribing please come back and refresh this page.
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 access the code.
After subscribing please come back and refresh this page.
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:
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn