Fast generation of permutations

Frode Øijord frodo at sim.no
Wed Jan 25 15:33:48 CET 2006


Hi all,
given a sequence of n elements i need to generate all possible 
permutations of length k <= n.

I found an elegant way to do this recursively:

def comb(items, n):
     if n==0: yield []
     else:
         for i in xrange(len(items)):
             for cc in comb(items[i+1:],n-1):
                 yield [items[i]]+cc

However, this is way too slow for my needs. I try to use this to 
generate all possible 5 card poker hands, but this takes around 17 
seconds on an Athlon 2200. That's a 2 orders of magnitude too slow for 
my needs.

I am familiar with writing Python extensions in C++, but I will not do 
this until I am confident that it is the only way to get the speed I need.

Any of you excellent sirs have any suggestions on how I can speed this up?

Please find attached an example script that executes and times the poker 
hand generation.


-- 
Frode, SIM

"Any fool can write code that a computer can understand.
  Good programmers write code that humans can understand"
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: permutations.py
URL: <http://mail.python.org/pipermail/python-list/attachments/20060125/15e9b051/attachment.ksh>


More information about the Python-list mailing list