5
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Sorry, looks like I edited my code while you were writing that. I had a feeling this might be the case, was just off to write a test harness to check the random distribution. So in the new code (second function), array.length should be (array.length + 1), correct? \$\endgroup\$ – Dagg Feb 9 '12 at 2:41
  • \$\begingroup\$ I reviewed the unfactored version. I'm pretty sure the same bug still lurks. Also, the new code seems weird: Is it a safe no-op to array.push(array[0]) on an empty array? \$\endgroup\$ – Paul Martel Feb 9 '12 at 2:42
  • \$\begingroup\$ yeah that part's safe, if you click the demo and then click the thing in the upper right hand corner you can edit the code live, shuffle stuff is at the bottom \$\endgroup\$ – Dagg Feb 9 '12 at 2:44
  • \$\begingroup\$ So, it seems that array.push(array[j]) is safe even accounting for the possibility of j == array.length -- it's just a little wierd. It's exactly the "completely safe assignment from uninitialized data" that the Wikipedia article warns about, but it gets a little confusing when you try to think of push as growing the array to include the exact non-pre-existent element that is being provided as its initializer. \$\endgroup\$ – Paul Martel Feb 9 '12 at 3:31
  • \$\begingroup\$ I've come back to look at it three times to make sure the push wasn't messing things up, but since it always happens first it's safe... yeah this is the thing the article warns (or "unwarns?") about \$\endgroup\$ – Dagg Feb 9 '12 at 5:53
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Is it always safe to detach random from Math like that? I'm wary of getting references to built-in functions. I feel like some implementation might need its this reference or something. \$\endgroup\$ – Dagg Feb 9 '12 at 6:30
  • \$\begingroup\$ Good question! I take functions as objects so blindly I had to do some research for the special Math object. I'm going to have to say yes: Here's an example where John Resig treats them directly as "normal" functions. \$\endgroup\$ – Adam Rofer Feb 9 '12 at 6:43
  • \$\begingroup\$ Take a look at the bottom of my question. I feel like this is probably safe in practice but i suspect that by definition it might be undefined behavior. I worked around it by changing the api to require an object with a random function property instead of a function. \$\endgroup\$ – Dagg Feb 9 '12 at 6:48
  • \$\begingroup\$ of course pushRand could probably be further optimized by doing something like pushRand.generator = rng before calling it instead of passing it in every time, but I'd just as soon come up with a better api altogether \$\endgroup\$ – Dagg Feb 9 '12 at 6:52
  • \$\begingroup\$ Well, I searched various compiled js sources (google websites, jquery-min, etc) and I couldn't find an instance where even those people used the Math methods any other way than "normally", so I'm not sure if there's really any risk or not. I think for the Math object you're safe, but others might have issues like you describe. That said, running this works fine in Chrome: var x = Math.random; alert(x()); \$\endgroup\$ – Adam Rofer Feb 9 '12 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.