On 27 Mar 2009, at 06:59, Imri Goldberg wrote:
On Thu, Mar 26, 2009 at 11:19 PM, Jan Kanis <jan.kanis@phil.uu.nl> wrote: Just out of curiosity, would doing
l = range(2082) random.shuffle(l) random.shuffle(l)
give me (with a high probability) one of those permutations that is unreachable with a single shuffle? If so, I'd presume you could get any shuffle (in case you really cared) by calling random.shuffle repeatedly and reseeding the prng in between.
I'm a bit rusty on the math, but that doesn't have to be the case. If all the permutations produced by random.shuffle() form a subgroup, or lie in a subgroup, then what you'll get is just another permutation from that subgroup, regardless of the randomness you put inside.
There is no reason that the set of shuffled permutations(S_n) will form a subgroup of the set of permutations (P_n) and it may well generate the whole of P_n. In fact you only need n transpositions to generate the whole of P_n. However, any function generates a random permutation is a function from the set of possible states of the PRNG to the set of permutations. Whatever tricks you use, if there are fewer states in the PRNG than there are permutations, you won't be able to reach them all. -- Arnaud