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

Terry Jones terry at jon.es
Mon Jun 12 03:19:57 CEST 2006

"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

More information about the Python-Dev mailing list