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

[Jacob Holm]

Arnaud Delobelle wrote:
>
> 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.
True, it is extremely likely that the group G_n generated by S_n is P_n 
and not a subgroup.

>
> 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.
>
You are right, you won't be able to reach them all in a single call to 
shuffle. However, by repeated shuffling and reseeding like the OP 
suggested, you can in theory get to all elements of G_n *if you keep 
shuffling long enough*. Unfortunately you will need at least |G_n|/|S_n| 
shuffles which means it is not even remotely practical.

- Jacob