[Python-Dev] a note in random.shuffle.__doc__ ...

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)
>>         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

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).


More information about the Python-Dev mailing list