Re: [FWP] Shuffling (was Re: [FWP] Perl Card Games)

[Bennett Todd <bet@newritz.mordor.net>]

1999-08-05-15:07:45 Amir Karger:
> Shuffling is a surprisingly tricky process. It's easy to write a bad
> shuffle:
> 
>     sub naive_shuffle { # don't do this
> 	for (my $i = 0; $i < @_; $i++) {
> 	    my $j = int rand @_;
> 	    ($_[$i], $_[$j]) = ($_[$j], $_[$i]);
> 	}
>     }
>[...]
> The Fisher-Yates shuffle avoids this bias by changing the range of
> the random numbers it selects.
> ----------------------------------------------------------------------
> 
> (As a reminder, Fisher-Yates is just like the naive shuffle, except you
> loop *down* instead of up, and take rand($i+1) instead of rand(@_).)

So Fisher-Yates looks like

	for (my $i = @_; $i > 0; $i--) {
		@_[$i, $_] = @_[$_, $i] for rand $i+1;
	}

That looks isomorphic to the way I'd thought of it, only counting back does
make it a bit neater. That's really starting to look quite sexy, in fact.

As far as I can see, though, your schwartzian shuffle and Fischer-Yates should
both be perfectly random (or rather, as good as the builtin prng, which in
recent years doesn't half suck). I suspect yours has a potential for a wee
teensy theoretical bias; if you rand should happen to croak out two identical
floats within the run, and if your qsort should happen to be a stable sort,
then the stability of the sort will shine through and refrain from reordering
the two elements that got assigned equal "random" numbers. I suspect the odds
of that happening can be neglected:-). On the other hand I'd always
mis-implemented Fisher-Yates, when I coded it with swaps, so it forced every
card in the deck to move into a different spot, rather than giving it its
one-in-N chance of remaining unmoved. A substantially worse error.

Mostly, though, your shuffle just makes the machine work a bit harder; doing
N-1 rands and swaps is appreciably cheaper than doing N rands and an
O[n log n] sort.

-Bennett

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe