I've implemented two different versions of the Fisher-Yates shuffle in javascript, and I'd like to know if I've made any mistakes.
I'm creating a deck of playing cards. I'm interested in these shuffle algorithms.
The object passed to the rng
parameters below is a wrapper for Johannes Baagøe's Alea, a seedable PRNG that should produce a better sample of random numbers than built-in Math.random
. Its API is the same as that of Math.random
.
I am mostly wondering if I have made any fencepost errors or misunderstood the examples I'm referencing.
/** shuffle
Shuffle an array.
@see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
@param {Array} array
@param {Function} random Optional RNG. Defaults to Math.random.
@return {Array} The original array, shuffled.
*/
function shuffle (array, random) {
var i = array.length, j, swap;
while (--i) {
j = (random ? random() : Math.random()) * (i + 1) | 0;
swap = array[i];
array[i] = array[j];
array[j] = swap;
}
return array;
}
/** pushRand
Insert a value into an array at a random index. The element
previously at that index will be pushed back onto the end.
@see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_.22inside-out.22_algorithm
@param {Array} object to shuffle.
@param {Mixed} value to insert.
@param {Function} optional RNG. Defaults to Math.random.
@return {Number} The new length of the array.
*/
function pushRand (array, value, random) {
var j = (random ? random() : Math.random()) * array.length | 0;
array.push(array[j]);
array[j] = value;
return array.length;
}
Here's a demo of the shuffle. Reloading the page does the inside-out shuffle, and clicking the face-down card does the modern shuffle.
Edit: I found a fencepost error in the "modern" version and fixed it here, but it's still in the demo. Not sure about the "inside-out" version yet.
Edit: I stopped being lazy and factored this stuff out, so it should easier to look at now. New demo up.
Edit: inside-out ver had the fencepost error too. It should look like this, I think:
function pushRand (array, value, random) {
var j = (random ? random() : Math.random()) * (array.length + 1) | 0;
array.push(array[j]);
array[j] = value;
return array.length;
}
Thanks, Paul!
Edit: Taking Adam's optimization suggestion into account, the new code looks like this:
/** shuffle
Shuffle an array.
@see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_.22inside-out.22_algorithm
@param {Array} array Array to shuffle.
@param {Object} rng Optional RNG. Defaults to Math.
@return {Array} The original array, shuffled.
*/
function shuffle (array, rng) {
var i = array.length, j, swap;
if (!rng) rng = Math;
while (--i) {
j = rng.random() * (i + 1) | 0;
swap = array[i];
array[i] = array[j];
array[j] = swap;
}
return array;
}
/** pushRand
Insert a value into an array at a random index. The element
previously at that index will be pushed back onto the end.
@see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
@param {Array} array Array to insert into.
@param {Mixed} value Value to insert.
@param {Object} rng Optional RNG. Defaults to Math.
@return {Number} The new length of the array.
*/
function pushRand (array, value, rng) {
var j = (rng || Math).random() * (array.length + 1) | 0;
array.push(array[j]);
array[j] = value;
return array.length;
}
Here's the updated editable demo (relevant code at the bottom).