On Jun 10, 2006, at 1:08 PM, Josiah Carlson wrote: > Josiah Carlson <[EMAIL PROTECTED]> wrote: >> >> Alex Martelli <[EMAIL PROTECTED]> 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) >> log_2(2**19997) < log_2((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 _______________________________________________ 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
