The only way to shuffle an array in JavaScript
There’s an old programming interview question where you’re asked to come up with an algorithm for shuffling a deck of cards.
“So, how would you shuffle a deck of cards?”
“Umm… Pick two random numbers. Swap the cards at those positions. Repeat until the deck’s shuffled.”
“Okay. Let’s pretend I’m a random number generator. Walk me through your solution.”
“Give me a random number.”
“Three.”
“Okay. Give me another random number.”
“Three.”
“Umm… Well… Yeah, having a card not change places is okay. So I take the card at position three and swap it with itself. Which is a no op.”
“What happens next?”
“We do it again. Give me another random number.”
“Three.”
“How about another random number?”
“Three.”
The lovely thing about randomness is that it’s random. It’s totally possible that you could roll a six sided dice four times and get a three each time, but it’s not very probable. Something like a 77 in 100,000 chance.
0.00077 ≈ 14 64
Computers aren’t great an generating really random numbers. The best they can do is pseudo random numbers. Depending on the language and library you’re using, you might get nicely distributed numbers, or you might get threes every time. The trick is knowing what to do with that.
All the JavaScript games I’ve made share this common piece of code. It’s a function for shuffling an array in place.
function shuffle (array) {
var i = 0
, j = 0
, temp = null
for (i = array.length - 1; i > 0; i -= 1) {
j = Math.floor(Math.random() * (i + 1))
temp = array[i]
array[i] = array[j]
array[j] = temp
}
}
That’s a Fisher-Yates shuffle. It was invented by Ronald Fisher and Frank Yates in 1938, originally as a method for researchers to mix stuff up with pencil and paper. In 1964, Richard Durstenfeld came up with the modern method as a computer algorithm. It has a run time complexity of O(n).
I first encountered the Fisher-Yates shuffle in 2005 when I was asked the “How would you shuffle a deck of cards?” question during an interview. Since then, it’s been one of those algorithms that I keep around in my video game development hand bag.
Would you like to know more?
Mike Bostock’s post “Fisher-Yates Shuffle” (2012) has lovely examples that animate shuffled decks of cards. Watching cards animate and seeing when collisions happen gives you a very real feel for how long it takes a bad shuffling algorithm to finish.
Jeff Atwood’s post “The Danger of Naïveté” (2007) illustrates why the Fisher-Yates shuffle is unbiased. He compares all possible outcomes for a naïve shuffle vs. a Fisher-Yates shuffle and works through the statistics to explain why the naïve shuffle is broken.