Shuffle

The Problem

Recreate the functionality of the Underscore.js _.shuffle function.

Understanding the Problem

Shuffling algorithms can be considered the opposite of sorting algorithms. The goal of the shuffle function is to randomize the content of an array (for this exercise, I limited my versions of the shuffle function to accept only arrays) so that there is no particular order based on any criteria whatsoever.

Various Versions

Fisher-Yates Shuffle

A simple Google search showed me that the most popular shuffling algorithm is Fisher-Yates Shuffle. This algorithm starts by looking at the whole range of indices in the array and then swapping the value in the last index with the value in a random index within the range of indices. On the next iteration, the range of indices shrinks by 1 since the last element in the array has already been placed with the shuffle. The array is effectively being divided into an already-shuffled section and a to-be-shuffled one. This continues until the whole array has been shuffled. And since every permutation is equally likely, this algorithm is unbiased.

Here’s a table view of what is happening for the array [0,1,2,3].

Below is my implementation of _.shuffle.

_.shuffle = function(array) {
  var newArr = array.slice();
  for (var i=array.length-1; i>0; i--) {
    var rand = Math.round(Math.random() * i);
    var temp = newArr[rand];
    newArr[rand] = newArr[i];
    newArr[i] = temp;
  }
  return newArr;
};

Using Sort

There is also a clever way to make _.shuffle using a customized sort() method.

_.shuffle = function(array) {
  return array.slice().sort(function() { return Math.random() - 0.5; });
};

However, this isn’t necessarily completely random. The elements will be biased towards their original positions in the array.

For more information about these two methods of shuffling, check out this Stack Overflow post. I especially appreciated Christoph’s discussion and his implementation.

Christoph’s implementation on Stack Overflow

function shuffle(array) {
  var tmp, current, top = array.length;
  if(top) while(--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }
  return array;
}

The Underscore.js Source

The original underscore shuffle function takes any sort of collection, not just arrays.

_.shuffle = function(obj) {
  var rand;
  var index = 0;
  var shuffled = [];
  each(obj, function(value) {
    rand = _.random(index++);
    shuffled[index - 1] = shuffled[rand];
    shuffled[rand] = value;
  });
  return shuffled;
};

And here’s a mixin to extend Underscore’s shuffle to use Fisher-Yates that I found here.

_.mixin({
  shuffle : function(obj) {
    var shuffled = [], rand;
    _.each(obj, function(value, index, list) {
      if (index == 0) {
        shuffled[0] = value;
      } else {
        rand = Math.floor(Math.random() * (index + 1));
        shuffled[index] = shuffled[rand];
        shuffled[rand] = value;
      }
    });
    return shuffled;
  }
});