[Numpy-discussion] Permutation in Numpy

[Hee-Seng Kye]

Thank you so much for your suggestion!  You are right that I only need  
to access permutations of 12 in order, so your suggestion of using  
generator is perfect.  In fact, I only need to access first half of  
permutations of 12 that begin on 0 (12! / 12 / 2, about 20 million), so  
the last code you offered would really speed things up.  Thanks again.

Best,
Kye

On Jul 28, 2004, at 7:05 PM, David M. Cooke wrote:

> 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
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by BEA Weblogic Workshop
> FREE Java Enterprise J2EE developer tools!
> Get your free copy of BEA WebLogic Workshop 8.1 today.
> http://ads.osdn.com/?ad_id=4721&alloc_id=10040&op=click
> _______________________________________________
> Numpy-discussion mailing list
> Numpy-discussion at lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/numpy-discussion
>