[Numpy-discussion] Permutation in Numpy

[David M. Cooke]

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:
12! is about 0.5 billion, which is about as much RAM as your machine
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