Fast generation of permutations

[Jack Diederich]

On Wed, Jan 25, 2006 at 03:33:48PM +0100, Frode ?ijord wrote:
> 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.
> 

You might want to look at a specific purpose library for poker hands:
http://pokersource.sourceforge.net/

It has python bindings and is included in Debian based distributions
as the 'pypoker-eval' package.

If you really want to do combinations a C extension has already 
been written (by me).

http://probstat.sourceforge.net/

import probstat
cards = range(52)
for (hand) in probstat.Combination(card, 5):
  pass

Takes 1.3 seconds on my laptop instead of 17 seconds for the pure
python version which is only one order of magnitude faster.
Creating and populating 2598960 list objects one at a time isn't free!

for (i) in xrange(2598960):
  l = []

Takes 0.8 seconds on the same machine.

-jack