While updating a site our shop created for Google, I needed to find a way to randomize a finite set of items.  Little did I know that while performing a typical random sort on an array may certainly create a randomized set of results, the results are biased.

The typical, lazy random sort works like so:

function RandomSort (a,b) {
return (0.5 - Math.random());
}

But if your goal is to reach a truly normalized and equal distribution of results, this method is flawed as it will always favor at least one member of your finite set.  For a better explanation, read this.

The fix is to implement an algorithm that works essentially the same way as picking cards from a hat:  you randomly choose one member from the set, remove it from the set, decrease the range of your set by 1 and repeat until you reach the last member of your set.  This is what the Fisher-Yates shuffle is all about.

Here’s a javascript implementation of the more modern Durstenfeld algorithm:

function arrayShuffle(aArray) {

var mTemp,j,i=aArray.length;

while (i) {

j = Math.floor(Math.random() * i);
mTemp = aArray[--i];
aArray[i] = aArray[j];
aArray[j] = mTemp;

}
}

I tested this over 1,000 10,000 and 100,000 iterations and the results were essentially the same.  The variation over all the results was the was less than 10%.  BAM!

So there you have it.  If you ever need a truly random permutation of a finite set where the results are equally distributed, this is the way to go.