Fast generation of permutations
Frode Øijord
frodo at sim.no
Wed Jan 25 09:33:48 EST 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