[Python-ideas] [Python-Dev] About adding a new iterator methodcalled "shuffled"

[Jacob Holm]

Mark Dickinson wrote:
> On Tue, Mar 24, 2009 at 6:29 PM, Antoine Pitrou <solipsis at pitrou.net> wrote:
>   
>> On the other hand, sorting is O(n.log(n)), which is probably sub-optimal for
>> shuffling (I don't know how shuffle() is internally implemented, but ISTM that
>> it shouldn't take more than O(n)).
>>     
It doesn't.

>
> I assumed that the OP was suggesting something of the form:
>
> def shuffled(L):
>     while L:
>         i = random.randrange(len(L))
>         yield L[i]
>         L.pop(i)
>
> fixed up somehow so that it's only O(1) to yield each element;  in effect,
> an itertools version of random.sample.  
Like this, for example:

def shuffled(L):
    L = list(L) # make a copy, so we don't mutate the argument
    while L:
        i = random.randrange(len(L))
        yield L[i]
        L[i] = L[-1]
        L.pop()

Or this:

def shuffled(L):
    D = {} # use a dict to store modified values so we don't have to mutate the argument
    for j in xrange(len(L)-1, -1, -1):
        i = random.randrange(j+1)
        yield D.get(i, L[i])
        D[i] = D.get(j, L[j])


The second is a bit slower but avoids copying the whole list up front, 
which should be better for the kind of uses you mention.
And yes, I think it is necessary that it doesn't modify its argument.
> I could see uses for this
> in cases where you only want a few randomly chosen elements
> from a large list, but don't necessarily know in advance how many
> elements you need
So could I, but I don't mind too much having to write it myself when I 
need it.

- Jacob