Fisher-Yates shuffle algorithm in javascript, modern and inside-out versions

Question

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).

Answer 1

Unless you modify the inside out code to scale by (index+1)

       randomIndex = rand()*(index+1)|0;

You will not be covering all the possibilities. For index == 0, you always generate 0 -- this is correct, but only by accident.

For index == 1, you also always generate 0 -- instead of a 50/50 split between 0 and 1

The second card in the deck misses its ONLY chance to get to be card[1].

The same problem continues for each card from then on, without the +1, randomIndex < index when you want randomIndex <= index.

The problem may be even clearer for the last card placed in the deck. For a 52 card deck, index == 51, so randomIndex can be at most 50. So any prior card has a possibility of ending up at card[51], but not the last card. It can get no closer than card[50].

It should be reassuring that this change makes the math for the initial shuffle look more like that of the re-shuffle.

Answer 2

Note that you can optimize the first line inside the while loop:

 function shuffle (array, random) {
    var i = array.length, j, swap;
    while (--i) {
      j = (random ? random() : Math.random()) * (i + 1) | 0;

The check for random's boolean value happens each time (depending on the compiler, I imagine some optimize around it nicely). It's likely to run a bit faster like this:

 function shuffle (array, random) {
    var i = array.length, j, swap;
    random = random || Math.random;
    while (--i) {
      j = random() * (i + 1) | 0;

Edit: had random |= incorrectly (which does binary OR) - replaced with random = random ||