March 27, 2009
12:45 p.m.
Greg Ewing wrote:
Jacob Holm wrote:
However, by repeated shuffling and reseeding like the OP suggested, you can in theory get to all elements of G_n
But then you need a sufficient number of distinct seed values, so you're back to the original problem.
Ehr, no. Suppose my PRNG only has period two and the shuffle based on it can only generate the permutations [1, 0, 2] and [2, 1, 0] from [0, 1, 2]. Each time I reseed from a truly random source, the next shuffle will use one of those permutations at random. By shuffling and reseeding enough times I can get all combinations of those two permutations. This happens to be all 6 possible permutations of 3 elements. - Jacob