[Python-Dev] a note in random.shuffle.__doc__ ...
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