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) >> 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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4