How to shuffle an array

This is a very common programming problem, e.g. when you wish to show some images in random order, when you want to show a random quote, etc. I will show you a solution in JavaScript, but it can be ported to other languages easily.

The common solution to shuffling is to swap random elements, but swapping means you have to constantly work with two elements, and it can be done by using only one. Also, it’s common to randomly swap e.g. 1000 elements, but that wouldn’t work well for very large arrays.

All you have to do is follow a couple of simple steps:

  1. First, of course you start with a simple array, which you have in a specified order.
  2. You place a random element in the output array, and remove the element
  3. Repeat step 2 until the array is empty

Here’s the full code

function shuffle(r) {
	var pos;
	var out = [];
	while (r.length > 0)	{
		pos = parseInt(Math.random()*r.length);
		out.push(r[pos]);
		r = r.slice(0,pos).concat(r.slice(pos+1, r.length));
	}
	return out;
}

Let’s examine the parts. First, the variables pos and out are defined, and out is initialized to an empty array.

	var pos;
	var out = [];

No we “loop” through the array. But, do note that this is not a real loop, in fact we’re constantly going to remove elements until the array is empty. So the simple check on length is enough here.

	while (r.length > 0)	{

We find a random element. For large arrays the Math.random() method can be considered unreliable, but then I mean really large.

		pos = parseInt(Math.random()*r.length);

Next, we add the random element to the output array, using push. Then we remove the element from the original array. This is done in three parts:

  1. get everything on the left of the element
  2. get everything on the right of the element
  3. concat these two arrays to form a new array

That is a really difficult way of removing just one element, but deleting an element from an array is not a native javascript method. John Resig wrote another version of delete

		out.push(r[pos]);
		r = r.slice(0,pos).concat(r.slice(pos+1, r.length));

And last but not least we return the new array:

	}
	return out;
}

Example

Here’s an example of calling the function, shuffling 52 integers

var r=[];
i=52;
while (i--)
	r.push(i);
alert(shuffle(r).join(','));

Extending Array

If you feel so inclined you can make it an extension of the Array object in javascript, like so:

Array.prototype.shuffle = function() {
	var r=this;
	... //rest of code
}

Note the additional "r=this" line.

Drawbacks

There are some drawbacks and warnings to take note of:

  • It can be slow for huge arrays, I would recommend it for arrays under 1000 items
  • It takes up additional space, since it creates a new array
  • The delete can be improved, by using e.g. John Resig’s version

A shorter ‘hack’

The following is a short hack that can most definitely suit one time needs. It’s a form of sorting randomly, which sounds weird, and it is, but it works. However, if the random value is not seeded again, the next time you run it you end up with the exact same sequence.

function shuffle(r) {
  r.sort(function() { return Math.random() } );
}

For more background see e.g. the Fisher Yates shuffle method (which by the way this is not, but this is).

About these ads

1 comment so far

  1. Larry Battle on

    Your shorter hack seems to not work.
    Math.random() returns a decimal value from 0 to 1 exclusively.
    The sort function excepts -1, 0 or 1 to determine if the first argument is less than, equal to, or greater than the second argument.
    So an array passed through your shuffle function will most likely be in the original order.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: