Home Original page

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

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