Random Shuffle

There are many occasions when we need to shuffle some numbers or other objects within an array. But not all languages provide you with the proper tools, so you need to code your own.

A simple shuffle would look like this:

function SimpleShuffle (objList){

// Loops through the list
for(i = 0; i < objList.length; i++){

// Picks a random position of the list
pos = Math.floor(Math.random() * (objList.length+1));

// Swaps the content between positions
temp = objList[i];
objList[i] = objList[pos];
objList[pos] = temp;

}

}

But there’s a big problem, this shuffle is biased. That is, some results have a higher probability of being picked than others.

Let’s look at a quick example.
We have the letters A, B and C and we shuffled them 10.000 times. This was the result:

biased shuffle Random ShuffleNot very balanced, is it?

This problem stems from this shuffle being inefficient. By looping through all the positions in the list, it’s swapping values that had been shuffled previously.

The Fisher-Yates shuffle on the other hand doesn’t suffer from bias problems:

function FisherYatesShuffle (objList){

// Loops through the list in reverse
for(i = objList.length; i > 0; i--){

// Picks a random position of the list
pos = Math.floor(Math.random() * i);

// Swaps the content between positions
temp = objList[i];
objList[i] = objList[pos];
objList[pos] = temp;

}

}

unbiased shuffle Random Shuffle

The difference is subtle, but a powerful one.

Besides travelling through the list backwards, it only picks a random position from the ones it hasn’t visited yet. Which means it won’t perform unnecessary duplicate work.

You may also like...