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

[Alex Martelli]

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