Sunday, January 24, 2010

Permutations done right

In the last post (about dups in permutations), I forgot to mention the correct way to handle this problem. It is to use itertools.permutations (docs).

>>> from itertools import permutations as perms
>>> L = range(10)
>>> g = perms(L)
>>> rL = [g.next() for i in range(5000)]
>>> len(set(rL))
5000


These are in sorted order.

>>> rL[0]
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
>>> rL[1]
(0, 1, 2, 3, 4, 5, 6, 7, 9, 8)

You need to do random.shuffle if you want them in random order.

Perhaps there is a better way that I don't know? What I'd like is to get a generator that can give the next permutation at random, without the chance of a dup, and without constructing an actual list of all 10! elements.