Alex Martelli 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.

Now -- why would the behavior of "most" random number generators be relevant here? The module's docs claim, for its specific Mersenne Twister generator, a period of 2**19997-1, which is (e.g.) a comfortable 130128673800676351960752618754658780303412233749552410245124492452914636 028095467780746435724876612802011164778042889281426609505759158196749438 742986040468247017174321241233929215223326801091468184945617565998894057 859403269022650639413550466514556014961826309062543 times larger than the number of permutations of 2000 items, which doesn't really feel to me like a "rather small len(x)" in this context (what I'm most often shuffling is just a pack of cards -- len(x)==52 -- for example).

I wouldn't be too comfortable with that margin. The fun thing about factorials is that they add up really quickly. The crossover point is between 2080 and 2081. In [28]: from scipy import * In [29]: def f(x): ....: return special.gammaln(x-1) - 19937*log(2) ....: In [30]: optimize.brentq(f, 2000, 3000) Out[30]: 2082.4031300820125 In [31]: import gmpy In [32]: mtperiod = 2**19937 - 1 In [33]: for i in range(2075, 2085): ....: if gmpy.fac(i) > mtperiod: ....: print i ....: break ....: ....: 2081 I think that documenting this boundary might be worthwhile rather than making vague references to "small len(x)." A note along the lines of Josiah wrote about there being no guarantees despite period size would also be useful. OTOH, isn't the exact PRNG algorithm considered an implementation detail? It certainly was when the module migrated from Wichmann-Hill to the Mersenne Twister. OTGH, I don't foresee the random module ever using an algorithm with worse characteristics than the Mersenne Twister. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco

[Alex Martelli]

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

Now -- why would the behavior of "most" random number generators be relevant here? The module's docs claim, for its specific Mersenne Twister generator, a period of 2**19997-1, which is (e.g.)

Oops! That's wrong. The period is 2**19937-1.

a comfortable 130128673800676351960752618754658780303412233749552410245124492452914636 028095467780746435724876612802011164778042889281426609505759158196749438 742986040468247017174321241233929215223326801091468184945617565998894057 859403269022650639413550466514556014961826309062543 times larger than the number of permutations of 2000 items, which doesn't really feel to me like a "rather small len(x)" in this context (what I'm most often shuffling is just a pack of cards -- len(x)==52 -- for example).

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!

It should be removed now. I'll do that :-) WH's period was indeed so short that it couldn't generate even a tiny fraction of the permutations of a deck of cards, and that's why the note was added. While a long period is necessary to get a shot at all permutations, it's not sufficient, and I don't know what the true story is wrt the Twister. For example, a miserable PRNG that returns 0.1, 0.1, 0.2, 0.1, 0.2, 0.2, 0.1, 0.2, 0.2, 0.2, 0.1, 0.2, 0.2, 0.2, 0.2, ... has infinite period, but has few (O(N)) distinct subsequences of length N. That's a failure of so-called equidistribution in N dimensions (for sufficiently large N, some N-vectors appear more often than others across the whole period). "A long" period is necessary but not sufficient for high-dimensional equidistribution. Off the top of my head, then, since the Twister is provably equidistributed in 623 dimensions to 32-bit accuracy, I expect it should be able to "fairly" generate all permutations of a sequence of <= 623 elements (equidistribution in N dimensions implies equidistribution in all dimensions <= N). So I'm happy to leave a warning out until the casinos switch to 12-deck blackjack ;-)