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

Josiah Carlson jcarlson at uci.edu
Sat Jun 10 22:08:08 CEST 2006

Josiah Carlson <jcarlson at uci.edu> wrote:

Alex Martelli <aleaxit at gmail.com> wrote: > > ...claims: > > Note that for even rather small len(x), the total number of > permutations of x is larger than the period of most random number > generators; this implies that "most" permutations of a long > sequence can never be generated. [snip] > I suspect that the note is just a fossil from a time when the default > random number generator was Whichman-Hill, with a much shorter > period. Should this note just be removed, or instead somehow > reworded to point out that this is not in fact a problem for the > module's current default random number generator? Opinions welcome! I'm recovering from a migraine, but here are my thoughts on the topic... The number of permutations of n items is n!, which is > (n/2)^(n/2). Solve: 2**19997 < (n/2)^(n/2)_ _log2(2**19997) < log2((n/2)^(n/2))_ _19997 < (n/2)*log(n/2)_ _Certainly with n >= 4096, the above holds (2048 * 11 = 22528) - Josiah

I would also point out that even if MT had a larger period, there would still be no guarantee that all permutations of a given sequence would be able to be generated from the PRNG given some aribtrary internal state.

More information about the Python-Dev mailing list