• 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 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:
  1. Shuffle the first (N - 1) items of the given sequence.
  2. 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 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 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:



The above content is written by:

Abhishek Dey

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

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave