Randomizing arrays

#algorithms #arrayshuffle #javascript #random

A little while back I had to make a card game in the browser. As with all card games, there is a need to shuffle the cards.

"Great!", you might think. "Sounds easy enough! Just call the .randomize() or .shuffle() method on the array.", is a normal plan and assumption... until you realize your language of choice does not implement such a feature for you.

I ran into this issue and needed to find a solution. Luckily for me, I had recently played around with some algorithm challenges and remembered an algorithm called the "Knuth shuffle", after the great Donald Knuth.

To be fair, he was the one popularizing the algorithm, but the current version, adapted for computers, was made by Richard Durstenfeld, based on the works of Frank Yates and Ronald Fisher, the Fisher-Yates shuffle.

The algorithm - in plain English

The goal of the algorithm is to provide a sufficiently pseudo-random shuffling of the given array for most use-cases, though not for cryptography.

Typically the algorithm starts at the last element, working towards the first, picking a random element of the elements preceding the current element. This way we keep track of already shuffled elements in an easy and non-complicated way.

Given the index i and that i > 0 is true, then take a random number between 0 and i-1 inclusive. Let's name this r.

Next we need to swap the elements using a temporary storage.

In temporary storage t, store the randomly picked element: t = array[r]. In the randomly picked index location array[r], store the current index element array[i]: array[r] = array[i]. Lastly set the current index location to the randomly picked element stored in t: array[i] = t.

Now, if i is still larger than 0, do it all again.

The algorithm - in JavaScript

This algorithm works in most, if not all, languages, as it is language agnostic, but some languages has this type of functionality built in, and that might be an even better solution if you want good statistical spread.

Anyhow, JavaScript was where I encountered the need, so here it is, fleshed out with comments.

var rand, tmp, array = [1,2,3,4,5,6,7,8,9];

// Start at the last index (length - 1),
// loop while i is bigger than 0,
// decrement i with one for each pass
for(var i = array.length -1; i > 0; i--){
    // Get the random number
    rand = Math.floor(Math.random() * i);

    // Store the randomly picked element in the temp variable
    tmp = array[rand];

    // Set the randomly picked index to be current element
    array[rand] = array[i];

    // Set the current index to be the randomly picked element
    array[i] = tmp;
}

Summary

Now as you see, this algorithm is actually quite efficient as well. It uses only one pass of the array to do its job, which means it runs in O(n) in Big-O notation. It also doesn't use any additional arrays, or shifting of arrays, which means that the only real overhead it has, is the storage for the temporary value and the random value.

Here is another piece of trivia for you, the Fisher-Yates shuffle was created in 1938 and converted to computers by Durstenfeld in 1964. The conversion also reduced the run time from O(n²) to O(n) as we see here.

Well, I for one enjoyed writing this, and I hope you enjoyed reading it. Leave a comment below if you use other algorithms for this use case or just want to share some other insight or comment on this.

Cheers!

-Morten