Fisher-Yates

The Fisher-Yates randomizing shuffle algorithm is widely known in Perl. I wanted to use it in JavaScript. I was surprised to not be able to find a simple or clear example of this online since it’s so easy to find in other languages. I took a stab at it and was surprised. It was easy to do. [Ed: there has been a correction to the code, noted below.]

This is a case where you get to see how similar Perl and JavaScript can be because of their shared heritage in C.

# not the best implementation for large arrays
sub fisher_yates {
    my $i = @_;
    return unless $i;
    while( --$i ) {
        my $j = int rand( 1 + $i );
        @_[$i,$j] = @_[$j, $i];
    }
}

That’s fun that way but probably better written, as the perldocs suggest, this way.

sub fisher_yates_shuffle {
    my $list = shift;  # this is an array reference
    my $i = @{$list};
    return unless $i;
    while ( --$i ) {
        my $j = int rand( $i + 1 );
        @{$list}[$i,$j] = @{$list}[$j,$i];
    }
}

my @cards = ( 1 .. 52 );
fisher_yates_shuffle(\@cards);
my $my_card = shift @cards;
my $your_card = shift @cards;
print 
    "Low card does dishes. I drew $my_card.\n",
    "   You drew $your_card.\n", 
    $my_card > $your_card ? "Ha!\n" : "D'oh!\n";

Low card does dishes. I drew 7.
   You drew 10.
D'oh!

function fisherYates ( myArray ) {
  var i = myArray.length;
  if ( i == 0 ) return false;
  while ( --i ) {
     var j = Math.floor( Math.random() * ( i + 1 ) );
     var tempi = myArray[i];
     var tempj = myArray[j];
     myArray[i] = tempj;
     myArray[j] = tempi;
   }
}

I don’t think we can do the in place swap that Perl lets us do but other than that, fisherYates() is entirely similar to fisher_yates_shuffle() in implementation.

<script type="text/javascript">
var asLucky = new Array ( 2, 3, 4, 5, 7, 9, 11, 13 );
fisherYates(asLucky);
var yourNumber = asLucky[0];
document.write("Your lucky number is: <b>" + yourNumber + "</b>");
</script>

Correction!

David Sletten quite astutely notes that if we follow the 5.6 perlfaq4 snippet for Fisher-Yates we create a useless final pass in the loop.

The code above is updated so that the while loops rely on the pre-decrement, but it was listed, sadly for quite some time, with the post-decrement operator; ie: it was $i-- for the Perl and i-- for the JS when it should have been --$i and --i respectively. Why? David explains it very well.

I believe there is a minor error--the same in both Perl
implementations and the JavaScript version. At issue is the test
condition in your 'while' loop. You should be using the pre-decrement
--$i rather than post-decrement $i--. The problem is that at the end
of the iteration where $i is 1, the loop test takes place and the
value of $i-- is 1, which is true, so the loop executes now with $i =
0. This means that you're evaluating rand(1), which unfortunately is
not random at all--it always returns 0. Consequently your
implementations are not broken, but rather they perform a final
useless iteration swapping array element 0 with itself...If you switch
to --$i, then the test will fail after the iteration when $i is 1,
right when you want it to. For comparison, here's the implementation
from The Perl Cookbook:

sub fisher_yates_shuffle {
    my $array = shift;
    my $i;
    for ($i = @$array; --$i; ) {
        my $j = int rand ($i+1);
        next if $i == $j;
        @$array[$i,$j] = @$array[$j,$i];
    }
}

For what it's worth, I like your version better with the 'while' loop
rather than this incomplete 'for' loop. Also, the 'next' statement
here is unnecessary (it's not found in Donald Knuth's description of
the algorithm) and may even slow the code down.

David Sletten