Home Original page

[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