[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. _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
