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

[Josiah Carlson]

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.

 - Josiah