[Python-ideas] About adding a new iteratormethodcalled "shuffled"

[Arnaud Delobelle]

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