[Python-Dev] a note in random.shuffle.doc ... (original) (raw)

Dan Christensen jdc at uwo.ca
Tue Jun 13 17:22:58 CEST 2006

Greg Ewing <greg.ewing at canterbury.ac.nz> writes:

Terry Jones wrote:

The code below uses a RNG with period 5, is deterministic, and has one initial state. It produces 20 different outcomes. You misunderstand what's meant by "outcome" in this context. The outcome of your algorithm is the whole sequence of numbers it produces, not each individual number.

I think Terry's point is valid. While no one call to random.shuffle(L) can produce every possible ordering of L (when len(L) is large), since random.shuffle shuffle's the data in place, repeated calls to random.shuffle(L) could in principle produce every possible ordering, since the "algorithm" is saving state. Down below I show code that calls random.shuffle on a 4 element list using a "random" number generator of period 13, and it produces all permutations.

(More generally, there's nothing to stop someone from changing the random.shuffle code to explicitly store more internal state to ensure that every permutation eventually gets produced. I'm of course not suggesting that this would be a good idea!)

In any case, the (old) text in the docstring:

    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.

is at least a bit misleading, especially the "never" part.

Dan

import random

i = 0 period = 13 def myrand(): global i i = (i+2)%period return float(i)/period

def countshuffles(L, num): L = list(L) S = set([])

for i in range(num):
    random.shuffle(L, random=myrand)
    S.add(tuple(L))

return len(S)

print countshuffles([1,2,3,4], 40)

More information about the Python-Dev mailing list