Implementing Java's Collections.Shuffle() In JavaScript
When I'm working with ColdFusion, and I need to shuffle an array of items, my default move is to pass the array down into the Java layer where I can leverage the Collections class. There, the shuffle() method makes sorting an array a simple task. The other day, I needed to shuffle a JavaScript array in the browser; so, I wanted to see if I could implement the same shuffle() algorithm in JavaScript. As it turns out, it's not too complicated.
After a little bit of Googling, I discovered that the Collections.shuffle() method uses the "Fisher-Yates" algorithm. This approach loops backwards over the array and swaps the current element with another randomly-selected element in the array. In the Java class, you can pass-in your own randomization method; or, you can use the internal one. I tried to replicate this feature by allowing an optional argument in the shuffle() method.
<!doctype html>
<html>
<head>
<meta charset="utf-8" />
<title>
Implementing Collections.Shuffle() In JavaScript
</title>
</head>
<body>
<h1>
Implementing Collections.Shuffle() In JavaScript
</h1>
<!-- Load scripts. -->
<script type="text/javascript">
// Define our collection object with exposed methods.
var collections = (function() {
// I generate a random integer between the min and max, both of which are
// inclusive in the range. If the "min" argument is omitted, the range is
// assumed to be zero-to-max.
function randRange( min, max ) {
// If only one argument, assumed to be Max.
if ( arguments.length === 1 ) {
max = arguments[ 0 ];
min = 0;
}
var range = ( max - min + 1 );
var offset = Math.floor( range * Math.random() );
return( min + offset );
}
// I shuffle the collection using the given rand-range implementation. If
// no implementation is provided, the default implementation is used.
// --
// NOTE: Uses the Fisher-Yates shuffle algorithm.
function shuffle( collection, randRangeImplementation ) {
// If a rand-range implementation is not provided, use the default.
if ( ! randRangeImplementation ) {
randRangeImplementation = randRange;
}
var length = collection.length;
var i = length;
// Loop backwards through the list, randomly swapping indices.
while( --i ) {
var j = randRangeImplementation( i );
if ( i !== j ) {
swap( collection, i, j );
}
}
return( collection );
}
// I swap the value at the given indices in the given collection.
function swap( collection, i, j ) {
var tempValue = collection[ i ];
collection[ i ] = collection[ j ];
collection[ j ] = tempValue;
}
// Return the public API.
return({
shuffle: shuffle
});
})();
// ------------------------------------------------------- //
// ------------------------------------------------------- //
// Let's try it out - build up a collection of numbers, shuffle, then output.
var numbers = [];
for ( var i = 1 ; i < 20 ; i++ ) {
numbers.push( i );
}
collections.shuffle( numbers );
console.log( numbers.join( ", " ) );
</script>
</body>
</html>
As you can see, we're building up an array of numbers, one through twenty, shuffling them, and then logging them to the console. When I run the page a few times, I get the following results:
9, 19, 4, 2, 5, 13, 7, 17, 12, 1, 8, 11, 18, 6, 16, 3, 15, 14, 10
19, 5, 13, 7, 4, 17, 3, 16, 11, 1, 9, 12, 15, 6, 2, 14, 18, 8, 10
3, 11, 8, 4, 5, 9, 7, 19, 18, 13, 15, 6, 2, 1, 17, 14, 16, 12, 10
19, 11, 4, 12, 9, 7, 14, 10, 17, 6, 16, 3, 15, 5, 13, 8, 18, 1, 2
18, 10, 14, 7, 19, 3, 1, 4, 16, 15, 2, 9, 5, 13, 11, 12, 8, 17, 6
7, 6, 3, 16, 15, 8, 2, 1, 5, 17, 14, 4, 19, 18, 12, 11, 9, 10, 13
Note that this approach, just as with Java's Collections.shuffle() method, shuffles the array "in place." Meaning, it doesn't return a new, shuffled copy of the array but, rather, the original array with updated values. This is different than several of the "functional" JavaScript libraries that return new arrays as the shuffled result.
To be honest, I didn't realize that the various functional JavaScript libraries (such as LoDash and Underscore) already had shuffle() methods until I was already writing this post. That said, it was interesting to learn more about this algorithm. Both in JavaScript and Java.
Want to use code from this post? Check out the license.
Reader Comments
Another option for shuffling a JavaScript array is passing a shuffle function into the native .sort() method.
Here is a post to a discussion on Fisher-Yates vs the above bubble sort approach.
http://stackoverflow.com/questions/962802/is-it-correct-to-use-javascript-array-sort-method-for-shuffling
@Bob,
That's an interesting approach. I'll have to read up the discussion a bit more. Thanks!
Mike Bostock did a pretty good explanation of the various approaches to JS shuffling here, with Fisher-Yates taking pride of place at the end:
http://bost.ocks.org/mike/shuffle
I found myself using it often enough to turn it into a gist and forget about it. Like you said, the best part has to be getting the original array back rather than a copy.
https://gist.github.com/blackmjck/8958066
Hi Ben,
given that the naive Array.sort based solution mentioned by Bob is maybe the worst one, it really seem like the Fisher-Yates rules. I tried to speed it up, obtaining good results [http://www.jmvc.org/test_arrayShuffle].
I even tried to test the three solutions suggested by Steven, but time are comparable to the Array.sort based or even worst.
Thank You for the cue.
@Steven,
Yooo, that page was awesome. I love the animations and it does a great job of illustrating why some of the approaches are slower. Great find!
@Federico,
Great exploration. I had to look up what the "~~" was doing. Bit-wise operations. Really interesting to see the variations, and how fast some of these things execute on such a large array!
@Federico
When valuing one approach over another I think it is important state the criteria. At times I've gone too far down the road of optimizing to later regret lack of clarity and simplicity of the code. I suspect for most it would be a rare occasion that required the need to shuffle 1000000 items. I think simple approach has merit for being simple, not for being optimized. But it might not be the best approach for all situations.
@Bob,
You`re absolutely right. I just wanted to share some digging