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

[Terry Jones]

>>>>> "Dan" == Dan Christensen <jdc at uwo.ca> writes:
Dan> 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. 

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

Maybe I should reiterate what I meant, as it seems the discussion is really
just semantics at this point.

Greg said:

    >>>>> "Greg" == Greg Ewing <greg.ewing at canterbury.ac.nz> writes:
    Greg> A generator with only N possible internal states can't
    Greg> possibly result in more than N different outcomes from
    Greg> any algorithm that uses its results.

And I replied:

    I don't mean to pick nits, but I do find this a bit too general.

    Suppose you have a RNG with a cycle length of 5. There's nothing to
    stop an algorithm from taking multiple already returned values and
    combining them in some (deterministic) way to generate > 5 outcomes.
    (Yes, those outcomes might be more, or less, predictable but that's not
    the point). If you expanded what you meant by "internal states" to
    include the state of the algorithm (as well as the state of the RNG),
    then I'd be more inclined to agree.

I was not meaning to say that anyone was wrong, just that I found Greg's
characterization a bit too general, or not as well defined as it might have
been.

It's clear, I think, from the example code that I and Dan posted, that one
can move the boundary between the RNG and the algorithm using it. You can
take a technique (like using lagging as I did, or Dan's method which stores
and composes permutations) out of the RNG and put it in the algorithm.
That's the reason I reacted to Greg's summary - I don't think it's right
when you confine yourself to just the internal states of the generator. As
I said, if you also consider the states of the algorithm, then the argument
is easier to defend. From an information theory point of view, it's simpler
not to draw the distinction between what's in the "RNG" and what's in the
"algorithm" that uses it. I guess we must all agree at that level, which to
me means that the recent discussion is necessarily just semantics.

[Tim's response to my first post wasn't just semantics - I was wrong in
what I said, and he made it clear (to me anyway) why. But at that point
there was no discussion of what any algorithm could produce as an outcome,
algorithm state, determinism, etc.]

And yes, you can also define outcome as you like. I deliberately included
the word 'outcome' in my print statement.  I thought that was definitive :-)

Terry