[Python-Dev] a note in random.shuffle.doc ... (original) (raw)

Tim Peters tim.peters at gmail.com
Sun Jun 11 00:44:01 CEST 2006

[Terry Jones]

That doc note should surely be removed. Perhaps it's an artifact from some earlier shuffle algorithm.

No, it's an artifact form an earlier PRNG. The shuffle algorithm hasn't changed.

The current algorithm (which is simple, well known,

Both true.

and which produces all permutations with equal probability)

That needs proof. Assuming a true random number generator, such a proof is easy. Using a deterministic PRNG, if the period is "too short" it's dead easy (see below) to prove that it can't produce all permutations (let alone with equal probablility).

only calls the RNG len(x) - 1 times.

And that's irrelevant. When a PRNG has period P, then no deterministic algorithm (for shuffling or anything else) using that PRNG can possibly produce more than P distinct outcomes: the position in the period when you start the algorithm entirely determines the outcome, and there are only P possible starting positions. For the older WH PRNG, P was much smaller than 52!, so it was just that easy to know that not all deck-of-card shufflings could be produced. The newer Mersenne Twister PRNG has a vastly larger period, and more to the point has provably excellent equidistribution properties in 52 dimensions.

More information about the Python-Dev mailing list