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 Baage'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).
Fisher-Yates shuffle algorithm in javascript, modern and inside-out versions
javascript;algorithm;shuffle
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 1The 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.