🙏

জয়  শ্রী  রাম

🕉

---

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 N^th element and randomly swap it with an element from the already shuffled first (N - 1) items.

Login to Access Content

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.


Login to Access Content




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:

• Reservoir Sampling

Instructor: