Re^5: Functional shuffle

[tlm]

Strictly speaking this is correct, but similar arguments apply in one way or another to any shuffling algorithm that relies on a PRNG, since the number of possible shuffled configurations can easily exceed the period of the PRNG, and even when it doesn't, the size of the set of possible numbers (2^k, where k is the number of bits available to represent these numbers) generated by the PRNG won't be evenly divisible by N!. The argument I made in my previous post was based on the simplifying assumption that the indexes used are real numbers in the unit interval (as opposed to, what is in fact the case, members of a large but finite set of rationals). In this case there is zero probability that in a set of N > 1 randomly chosen numbers in [0, 1] two will be equal, and therefore the problems introduced by the fact that the sorting is stable become irrelevant. True, in fact the probability that any two such numbers generated by a PRNG are equal is not quite zero, but it is very small.

[Anonymous Monk]

There a large difference between the fairness of the algorithm, and fairness of any implementation with practical constraints.

A sort-based shuffle is an algorithm that is not fair. It's rotten at the root. An implementation that suffers from an inperfect random generator has fairness problems due to environmental constraits.

Don't confuse the two things.