Re^4: Functional shuffle

[tall_man]

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.