from random import shuffle shuffle(s) I think it's convenient enough as is. Brandon

Mark Dickinson wrote:

On Tue, Mar 24, 2009 at 6:29 PM, Antoine Pitrou 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

On Wed, 25 Mar 2009 07:20:00 am Steven D'Aprano wrote:

On Wed, 25 Mar 2009 03:03:31 am Raymond Hettinger wrote:

...

...

On Tue, Mar 24, 2009, Roy Hyunjin Han wrote:

...

I know that Python has iterator methods called "sorted" and "reversed" and these are handy shortcuts.

Why not add a new iterator method called "shuffled"?

You can already write:

sorted(s, key=lambda x: random())

But nobody does that. So you have a good indication that the proposed method isn't needed.

That's nice -- not as readable as random.shuffle(s) but still nice. And fast too: on my PC, it is about twice as fast as random.shuffle() for "reasonable" sized lists (tested up to one million items).

Ah crap. Ignore the above: I made an embarrassing error in my test (neglected to actually call random inside the lambda) and so my timings were completely wrong. The current random.shuffle() is marginally faster even for small lists (500 items) so I withdraw my suggestion that it be replaced. -- Steven D'Aprano

Greg Ewing writes:

...

In addition, the F-Y shuffle is limited by the period of the random number generator:

*All* shuffling algorithms are limited by that.

Think about it: A shuffling algorithm is a function from a random number to a permutation. There's no way you can get more permutations out than there are random numbers to put in.

The period of the generator should be (much) larger than the number of possible random numbers, because of the generator's internal state. (I'm not sure I understood your sentence as you meant it though)