The Fisher-Yates shuffle algorithm is a very interesting question that you may have heard in your school or college asked in many interviews including FAANG companies.
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 effectively puts all the elements into a hat; it continually determines the next element by randomly drawing an element from the hat until no elements remain. The algorithm produces an unbiased permutation: every permutation is equally likely. The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place.
Given an array, generate the random permutation of array elements. It is similar to shuffling a deck of cards or randomizing an array and every outcome after shuffling of array elements should likely and equally.
This algorithm performs swapping a random element in the array with the last element in the array over and again.
Example 1:
Input: x = [2, 4, 6, 8, 10]
Output: [4, 10, 6, 2, 8]
[8, 10, 2, 6, 4]
Let's start with the algorithm,
var fisherYates = function(originalArray) {
// Clone array from preventing original array from modification (for testing purpose).
const array = originalArray.slice(0);
for (let i = (array.length - 1); i > 0; i -= 1) {
const randomIndex = Math.floor(Math.random() * (i + 1));
[array[i], array[randomIndex]] = [array[randomIndex], array[i]];
}
return array;
}
I hope you understood the algorithm. If you have any doubts, please let us know in the comments.
0 Comments