On Fri, Apr 18, 2008 at 10:27 PM, Stockly, Ed <[log in to unmask]> wrote:
>  Hmmm... Well, my concern is that every card should have an equal opportunity
>  to land at any position in the deck on every shuffle, and I'm just not
>  convinced that's happening here.


The Fisher-Yates algorithm gives each card an equal opportunity to
wind up at any position at the end of the algorithm.  Easy to
demonstrate: use a small list and replace the random number with a
loop through all the possible values that the random number can take
on. Record all the results and count up how often each element winds
up in each slot; you'll find that it's completely even across the
board.

The "swap with any item at any time" version gives one card an equal
opportunity to land at any position *at each step* of the algorithm,
but over the course of the whole trip you give out too many
opportunities and wind up with an uneven balance at the end.  This is,
again, easy to see if you use a small list and enumerate the results.
For example, with a three-item list, only the original first element
is equally likely to wind up anywhere.  The second element is most
likely to wind up first (37% chance),  slightly less likely to wind up
third (33%),  and even less likely to wind up still in second position
(30%). The third element  is most likely to wind up second, then
third, then first, with the same percentages.
-- 
Mark J. Reed <[log in to unmask]>