Advertisement
ActionScript

Quick Tip: How to Randomly Shuffle an Array in AS3

by

Sometimes you have a set of items -- could be Strings, could be Numbers, could be Objects, whatever -- whose order you want to randomise. This is particularly useful for quizzes and games of chance, but comes in handy in all sorts of other applications. The easiest method I've found for doing this is to stick all the items in an Array and then shuffle it like a deck of cards. But how can we do that...?

As a simple example, we'll use the letters of the alphabet:

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];

There are different approaches we can take to actually sorting this array.


The Naive Approach

We could create a second array, and copy each element of the first into a random position in the second:

The code for that might look like this (see this Quick Tip on getting a random integer within a specific range for more details):

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];
var shuffledLetters:Array = new Array(letters.length);

var randomPos:int = 0;
for (var i:int = 0; i < letters.length; i++)
{
	randomPos = int(Math.random() * letters.length);
	shuffledLetters[randomPos] = letters[i];
}

But there's one huge problem. What if the random position picked for C is 6 as well?

Here, A gets overwritten, and will therefore not be in the shuffled array. That's not what we want, so we need to check that the slot is empty before copying the letter over, and pick a different slot if it isn't:

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];
var shuffledLetters:Array = new Array(letters.length);

var randomPos:int = 0;
for (var i:int = 0; i < letters.length; i++)
{
	randomPos = int(Math.random() * letters.length);
	while (shuffledLetters[randomPos] != null)		//repeat as long as the slot is not empty
	{
		randomPos = int(Math.random() * letters.length);	//pick a different slot
	}
	shuffledLetters[randomPos] = letters[i];
}

That works. Problem is, it's inefficient. See, the letter A is guaranteed to fit into the slot picked, because it's the first letter chosen, so all the slots will be empty. With B, there's a 25 in 26 chance that the first slot picked will be empty. When we're half-way through the alphabet, this chance drops to 50/50. By the time we reach V, there's a 50/50 chance that we won't find an empty slot until the fourth attempt.

This means we're very likely to be calling Math.random() wayyyyy more than 26 times. And Math.random() is a relatively slow function. What's another approach we can take?


The Middle-Man Approach

What if we stored a list of all the empty slots in a third array, which would shrink as we went through them?

...and so on, repeating until the array of empty slots contains no elements. The code for that would look like this:

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];
var shuffledLetters:Array = new Array(letters.length);

var emptySlots:Array = new Array();
for (var n:int = 0; n < letters.length; n++)
{
	emptySlots.push(n);
}

var randomPos:Number = 0;
var actualSlot:Number = 0;
for (var i:int = 0; i < letters.length; i++)
{
	randomPos = int(Math.random() * emptySlots.length);		//note emptySlots.length not letters.length
	actualSlot = emptySlots[randomPos];
	shuffledLetters[actualSlot] = letters[i];
	emptySlots.splice(randomPos, 1);
}

Here we use the Array.splice() method to remove a single element from the list of empty slots. This actually removes the element, rather than just setting its value to null; so, after splicing the first slot, emptySlots.length will be 25 rather than 26.

This splice() function is great; we can use it for a third approach to shuffling that cuts out this middle man array.


The Splicing Approach

Instead of removing elements from the array of empty slots when we're done with them, we could remove them from the original, unshuffled array.

This doesn't sound very useful at first -- but what if we picked elements from the original array at random, instead of picking their destinations at random?

...and so on, until the first array contains no elements.

Unlike the other two approaches, we end up without the original array. Whether this is a problem or not depends on this project.

The code could look like this:

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];
var shuffledLetters:Array = new Array(letters.length);

var randomPos:Number = 0;
for (var i:int = 0; i < shuffledLetters.length; i++)	//use shuffledLetters.length because splice() will change letters.length
{
	randomPos = int(Math.random() * letters.length);
	shuffledLetters[i] = letters[randomPos];	//note this the other way around to the naive approach
	letters.splice(randomPos, 1);
}

In fact, since splice() returns an Array of all the elements you are splicing, we could simplify the code a little:<

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];
var shuffledLetters:Array = new Array(letters.length);

var randomPos:Number = 0;
for (var i:int = 0; i < shuffledLetters.length; i++)
{
	randomPos = int(Math.random() * letters.length);
	shuffledLetters[i] = letters.splice(randomPos, 1)[0];	//since splice() returns an Array, we have to specify that we want the first (only) element
}

That's neater. I've got one more approach to share; this one is very different to the others we've used so far.


The Sorting Approach

Arrays have a method, sort(), which by default rearranges all the elements of the array into ascending alphanumerical order, like so:

var mixedLetters:Array = ["G", "B", "P", "M", "F"];
mixedLetters.sort();
//mixedLetters is now ["B", "F", "G", "M", "P"]

You can pass options to this method, like Array.DESCENDING, which reverses the order of the sort:

var mixedLetters:Array = ["G", "B", "P", "M", "F"];
mixedLetters.sort(Array.DESCENDING);
//mixedLetters is now ["P", "M", "G", "F", "B"]

(There are other options, and you can pass as many of them as you like.)

You can also pass a reference to a function, which tells Flash how to decide which order any two items belong in. For example, this function could be used for numeric sorting:

function numericalSort(a:Number, b:Number):Number
{
	if (a < b) return -1;
	if (a == b) return 0;
	if (a > b) return 1;
}

Flash looks at each pair of adjacent items in the array, and rearranges them according to this function: it swaps them if the value 1 is returned, and leaves them alone otherwise. (Unless you pass Array.DESCENDING as well as the function, in which case it swaps them if the value -1 is returned, and leaves them alone otherwise.) Flash repeats this across the whole array over and over again until all pairs return 0 or -1 (0 or 1 if using Array.DESCENDING).

We can mess with this. Instead of giving it a genuine reason why any two elements should be swapped, we can just tell it to swap them at random, using a sort function like this:

function randomSort(a:*, b:*):Number	//* means any kind of input
{
	if (Math.random() < 0.5) return -1;
	else return 1;
}

Easy! Now we can use it in our code like so:

function randomSort(a:*, b:*):Number
{
	if (Math.random() < 0.5) return -1;
	else return 1;
}

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];
letters.sort(randomSort);

//(no need for the shuffledLetters[] Array)

Please note that the resulting array will not be as randomly shuffled as the other approaches we've used -- in this approach, there isn't an even 1/26 chance that any given letter will end up in any given slot. This is because we're only swapping adjacent pairs of elements, and doing no more than that. Still, it's a neat method :)

There are plenty of other methods, I know. Got any you like better than these?

Edit: Here's a great post with some very cool visualisations, explaining the Fisher-Yates shuffle, which works in place. I highly recommend it!

Related Posts
  • Design & Illustration
    Typography
    Mastering Calligraphy: How to Write in Gothic ScriptGothic script feature image
    In this "Mastering Calligraphy" lesson, we'll be learning what is by far the hardest font but also the most impressive. This font is a bit different than the others because it's made up of so many small strokes. However, the letters are very similar in construction so once you have a few down, you can do the rest easily! So let's get started!Read More…
  • Design & Illustration
    Typography
    Mastering Calligraphy: How to Write in Cursive ScriptCursive calligraphy feature image
    In this lesson of "Mastering Calligraphy" we're going to learn how to write like the great Jane Austen. Flowing, cursive lettering is still seen today on wedding invitations and menus at fancy restaurants. While it looks extremely difficult to ink, it's actually made of two basic strokes. Better yet, with the Cursive Script, you hardly ever have to lift your pen off the paper! So let's dive in to the Cursive Script.Read More…
  • Design & Illustration
    Typography
    Mastering Calligraphy: How to Write in Roundhand ScriptRoundhand script featured image for tutorial
    For our first tutorial in "Mastering Calligraphy", we're going to start with an easy alphabet that uses the two basic strokes we learned in the easy introduction. Just those two strokes make up a majority of the letters in the Roundhand Script alphabet. We'll be breaking the letters into similar groups and mastering both the lowercase and uppercase letters. So let's get started!Read More…
  • Code
    Corona SDK
    Corona SDK: Make a Word Drop GamePreview@2x
    In this tutorial, I'll teach you how to create a Word Drop game using the Corona SDK. We'll build the game from start to finish so I encourage you to follow along. In this tutorial, we will work with timers, physics, and implement our own touch controls. Let's get started.Read More…
  • Code
    JavaScript & AJAX
    Testing in Node.jsNodejs testing chai retina preview
    A test driven development cycle simplifies the thought process of writing code, makes it easier, and quicker in the long run. But just writing tests is not enough by itself, knowing the kinds of tests to write and how to structure code to conform to this pattern is what it's all about. In this article we will take a look at building a small app in Node.js following a TDD pattern.Read More…
  • Game Development
    Implementation
    Shuffle Bags: Making Random() Feel More RandomShuffle bag tutorial
    A pseudo random number generator (PRNG) like the Random Class in C# is not a true random number generator: its goal is to approximate randomness with speed. This means it will often return an uneven distribution of values, which may not be what you want. In this tutorial, I'll show you how to solve this problem with a shuffle bag.Read More…