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

[Terry Jones]

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

Greg> Terry Jones wrote:
>> 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.

Greg> No, it's not. As long as the RNG output is the only input to
Greg> the algorithm, and the algorithm is deterministic, it is
Greg> not possible get more than N different outcomes. It doesn't
Greg> matter what the algorithm does with the input.

Greg> If the algorithm can start out with more than one initial
Greg> state, then the RNG is not the only input.

The code below uses a RNG with period 5, is deterministic, and has one
initial state. It produces 20 different outcomes.

It's just doing a simplistic version of what a lagged RNG generator does,
but the lagged part is in the "algorithm" not in the rng. That's why I said
if you included the state of the algorithm in what you meant by "state" I'd
be more inclined to agree.

Terry

----

n = map(float, range(1, 17, 3))
i = 0

def rng():
    global i
    i += 1
    if i == 5: i = 0
    return n[i]

if __name__ == '__main__':
    seen = {}
    history = [rng()]
    o = 0
    for lag in range(1, 5):
        for x in range(5):
            o += 1
            new = rng()
            outcome = new / history[-lag]
            if outcome in seen: print "DUP!"
            seen[outcome] = True
            print "outcome %d = %f" % (o, outcome)
            history.append(new)


# Outputs
outcome 1 = 1.750000
outcome 2 = 1.428571
outcome 3 = 1.300000
outcome 4 = 0.076923
outcome 5 = 4.000000
outcome 6 = 7.000000
outcome 7 = 2.500000
outcome 8 = 1.857143
outcome 9 = 0.100000
outcome 10 = 0.307692
outcome 11 = 0.538462
outcome 12 = 10.000000
outcome 13 = 3.250000
outcome 14 = 0.142857
outcome 15 = 0.400000
outcome 16 = 0.700000
outcome 17 = 0.769231
outcome 18 = 13.000000
outcome 19 = 0.250000
outcome 20 = 0.571429