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

Alex Martelli aleaxit at gmail.com
Sat Jun 10 23:37:16 CEST 2006

On Jun 10, 2006, at 1:08 PM, Josiah Carlson wrote:

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.

Sure. And an n of 2081 happens to suffice:

period = 2**19937 while gmpy.fac(i) < period: i = i +1 ... i 2081

Still, the note, as worded, is misleading -- it strongly suggests
that for "even small len(x)" (no mention of whether that means dozens
or thousands) the RNG can't generate all permutations, with no proof
either way and just a misleading hint. "The values of N such that
the RNG can generate all permutations of a sequence of len(N) are not
precisely known at this time" might be closer to the truth (if this
is, indeed, the state of our collective knowledge).

Alex

More information about the Python-Dev mailing list