Shuffle Algorithms

In 1938, Ronald Fisher and Frank Yates developed the Fisher-Yates shuffle algorithm. It is a random, un-biased (all possibilities are equally likely) shuffle on a set of numbers, as shown below.

  1. List numbers 1..n
  2. Get random number k
  3. From low end, strike kth number
  4. Add struck number to results list
  5. Repeat until all numbers are struck
  6. Return results list

If this seems like it would create a very expensive function in terms of time complexity, it is. The lowest time complexity you can obtain on a shuffle is O(n) because you must iterate over the input at least once.

The most basic component of a JavaScript shuffle algorithm is the random property of the Math object. It generates a random number [0,1), meaning that it includes 0 but excludes 1. Math.floor() rounds down to the nearest integer.

Length = Length of list  
Key = Math.floor( Math.random() * length );  
List[Key]; // random item  

Note that this is a perfect setup for an array, where the length is 1 greater than the last index. Math.random() excludes 1, so the code above would never return length. The higest number this would return is length-1. If you are shuffling something that does not have numerical indices beginning at zero, you may need to watch out for this.

This is an example of a bad shuffle algorithm, where notShuffled is the original array.

shuffled = [];  
key = Math.floor(Math.random() * length);  
for (var i=0; i<length; i++) {  
    while (shuffled[key]) {
        key = Math.floor(Math.random() * length);
}
shuffled[key] = notShuffled[i];  
}      

This has a time complexity of O(n^2) or worse. It is possible that the while loop could run more times that there are elements in the array, especially near the end. Theoretically, the while loop could run infinitely.

This is an example of a good shuffle algorithm. It is in-place and has a time complexity of O(n). This algorithm does not repetitively call Math.random(). It swaps elements for each call to Math.random(), one per iteration.

for (var i=0, count=array.length; i < count; i++) {  
    var j = Math.floor(Math.random() * (count-i)) + i;
    var hole = array[i];
    array[i] = array[j];
    array[j] = hole;
}

Now that you know how to shuffle an array, go watch Imitation Game and reflect on how awesome Alan Turing was and how the shuffle algorithm was invented before the computer.

Additional Reading:
Wikipedia and this cool blog.