in reply to
Re^3: Functional shuffle
in thread Functional shuffle
I'm basing my objection to the sort-based shuffle on this note in the paper that Roy Johnson referenced:
Furthermore, if we have a sequence of N elements and associate with
each element a key -- a random number uniformly distributed within 0,
M-1 (where N!>M>=N), we have the configurational space of size M^N
(i.e., M^N ways to key the sequence). There are N! possible
permutations of the sequence. Alas, for N>2 and M<N!, M^N is not
evenly divisible by N!. Therefore, certain permutations are bound to
be a bit more likely than the others.
I would further argue that even when M (the period of the psuedo-random number generator) is larger than N, M^N is still not divisible by N! in general. The Fisher-Yates shuffle applies decreasing probabilities as it moves down the deck; the sorting shuffle uses uniform ones. That is the key difference.
I believe the discussion under A bad shuffle is also applicable.