Learn: Fisher–Yates shuffle in Javascript

The Fisher–Yates shuffle is an algorithm for generating generating a random permutation of a finite sequence. The good part of this algorithm is that it guarantees a very high efficiency and produces an impartial permutation: every permutation is equally likely. There are two version of this algorithm, the modern is the more efficent and in addition to requiring time proportional to the number of elements that are mixed it mixes them in place, therefore, without the use of auxiliary structures, this also increases the efficiency in memory.

The original method

The Fisher–Yates shuffle, in its original form, was designed to be used with pencil and paper. The original metod was:

1. Write down the numbers from 1 through N.
2. Pick a random number k between one and the number of unstruck numbers remaining (inclusive).
3. Counting from the low end, strike out the kth number not yet struck out, and write it down at the end of a separate list.
4. Repeat from step 2 until all the numbers have been struck out.
5. The sequence of numbers written down in step 3 is now a random permutation of the original numbers.

The modern method

The moder method was introduced by Richard Durstenfeld in 1964, there are only a simple but significant change, instead of needless time counting the remaining numbers in step 3, Durstenfeld’s solution is to move the “struck” numbers to the end of the list by swapping them with the last unstruck number at each iteration. This greatly reduces the complexity of the algorithm.

Implementation

Yes, it’s a just 7 lines implementation! Really simple and really efficient. Thx to the ES6 destructuring assignment that make us to make a swap without use another variables or using a splice , but is this the most efficent solution ? let’s check!