# [Numpy-discussion] Permutation in Numpy

David M. Cooke cookedm at physics.mcmaster.ca
Wed Jul 28 16:06:03 CDT 2004

```On Sun, Jul 25, 2004 at 07:24:49AM -0400, Hee-Seng Kye wrote:
> #perm.py
> def perm(k):
>     # Compute the list of all permutations of k
>     if len(k) <= 1:
>         return [k]
>     r = []
>     for i in range(len(k)):
>         s =  k[:i] + k[i+1:]
>         p = perm(s)
>         for x in p:
>             r.append(k[i:i+1] + x)
>     return r
>
> Does anyone know if there is a built-in function in Numpy (or Numarray)
> that does the above task faster (computes the list of all permutations
> of a list, k)?  Or is there a way to make the above function run faster
> using Numpy?
>
> I'm asking because I need to create a very large list which contains
> all permutations of range(12), in which case there would be 12!
> permutations.  I created a file test.py:

Do you really need a *list* of all those permutations? Think about it:
has. Each permutation is going to be a list taking 20 bytes of overhead
plus 4 bytes per entry, so 68 bytes per permutation. You need 32 GB of
RAM to store that.

You probably want to just be able to access them in order, so a
generator is a better bet. That way, you're only storing the current
permutation instead of all of them. Something like

def perm(k):
k = tuple(k)
lk = len(k)
if lk <= 1:
yield k
else:
for i in range(lk):
s = k[:i] + k[i+1:]
t = (k[i],)
for x in perm(s):
yield t + x

Then:

for p in perm(range(12):
print p

(I'm using tuples instead of lists as that gives a better performance
here.)

For n = 9, your code takes 9.4 s on my machine. The above take 3 s, and
will scale with n (n=12 should take 3s * 10*11*12= 1.1 h). Your original
code won't scale with n, as more and more time will be taken up
reallocated the list of permutations.

We can get fancier and unroll it a bit more:
def perm(k):
k = tuple(k)
lk = len(k)
if lk <= 1:
yield k
elif lk == 2:
yield k
yield (k[1], k[0])
elif lk == 3:
k0, k1, k2 = k
yield k
yield (k0, k2, k1)
yield (k1, k0, k2)
yield (k1, k2, k0)
yield (k2, k0, k1)
yield (k2, k1, k0)
else:
for i in range(lk):
s = k[:i] + k[i+1:]
t = (k[i],)
for x in perm(s):
yield t + x

This takes 1.3 s for n = 9 on my machine.

Hope this helps.

--
|>|\/|<
/--------------------------------------------------------------------------\
|David M. Cooke                      http://arbutus.physics.mcmaster.ca/dmc/
|cookedm at physics.mcmaster.ca

```