issue Issue in JavaScript Fisher Yates Shuffle Example

[SweatyWrangler]

What's the issue?

The example I am referring to is the Fisher Yates implementation on this page: https://www.w3schools.com/js/js_array_sort.asp

This is the code in question:

var points = [40, 100, 1, 5, 25, 10];

for (i = points.length -1; i > 0; i--) {
  j = Math.floor(Math.random() * i)
  k = points[i]
  points[i] = points[j]
  points[j] = k
}

If you run the example you will see the elements of the array shuffle around and everything will seem to be working as expected. The issue is subtle. With the above code block the element in the last position of the array can never remain in the last position of the array, and, with each iteration, the last element that is referenced can never remain in that position. 

Why can't the last element contain the same value after shuffle?

It has to do with this statement:

  j = Math.floor(Math.random() * i)

Because Math.random() generates a number between 0 and 1 which is inclusive of 0 but not inclusive of 1, the integer represented by i will never be assigned to j. With the above algorithm, i starts by referencing the last index of the array and therefore j can never be the last index.

Why does this matter?

This algorithm is supposed to produce an unbiased permutation of the elements meaning that every permutation is equally likely. With this shuffle, any element should have an equal chance of being shuffled into any position in the array including the position it already occupies.

"Yeah, but, why would this matter in REAL LIFE?"

In a practical example, I've needed to solicit feedback from users in a product. This was done by presenting a question with multiple possible answers. In order to prevent bias in the responses, the order the answers were presented was randomized for each person responding. From a code standpoint, each answer would have always started from the same position in the array. With this implementation, the last answer in the array would have never been the last answer presented to the user. This would have unknowingly introduced a different element of bias and skewed the results.

Updated Implementations

One possible update which still uses a for loop is to use the length of the array as the starting value of i and to decrement only after j has been randomly selected:

var points = [40, 100, 1, 5, 25, 10], i, j, k;

for (i = points.length; i > 0;) {
  j = Math.floor(Math.random() * i--)
  k = points[i]
  points[i] = points[j]
  points[j] = k
}

 

This looks a little wonky because even though the third statement in a for loop is optional, this is not a typical implementation. If we're going to decrement i inside of the code block, people typically use a while statement:

var points = [40, 100, 1, 5, 25, 10];
var i = points.length, j, k;
while (i > 0) {
  j = Math.floor(Math.random() * i--)
  k = points[i]
  points[i] = points[j]
  points[j] = k
}

I've also declared j and k before use. Generally it is considered good practice to declare variables before using them and using undeclared variables is not allowed in "strict mode".