[Python-ideas] About adding a new iteratormethodcalled "shuffled"
Arnaud Delobelle
arnodel at googlemail.com
Fri Mar 27 08:24:23 CET 2009
On 27 Mar 2009, at 06:59, Imri Goldberg wrote:
>
>
> On Thu, Mar 26, 2009 at 11:19 PM, Jan Kanis <jan.kanis at 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
More information about the Python-ideas
mailing list