Velocity Reviews > Fast generation of permutations

# Fast generation of permutations

=?ISO-8859-1?Q?Frode_=D8ijord?=
Guest
Posts: n/a

 01-25-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"

import sys
from timeit import Timer

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

def test():
cards = range(52)
for hand in comb(cards, 5):
"do something with the hand"

def main(argv):
t = Timer("test()", "from __main__ import test")
print t.timeit(1)

if __name__=="__main__":
sys.exit(main(sys.argv[1:]))

Jack Diederich
Guest
Posts: n/a

 01-25-2006
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

Michael Amrhein
Guest
Posts: n/a

 01-25-2006
Frode Ĝijord schrieb:
> 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.
>
>
>
> ------------------------------------------------------------------------
>
> import sys
> from timeit import Timer
>
> 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
>
>
> def test():
> cards = range(52)
> for hand in comb(cards, 5):
> "do something with the hand"
>
> def main(argv):
> t = Timer("test()", "from __main__ import test")
> print t.timeit(1)
>
>
> if __name__=="__main__":
> sys.exit(main(sys.argv[1:]))

If you don't need the flexibility of having the number of elements in
your permutation as a parameter - as it seems to be the case in your
poker example - simply use nested for-loops, 5 in this case.
Example for 5 out of 7 (just to keep the output shorter):
for i1 in range(7):
for i2 in range(i1+1,7):
for i3 in range(i2+1,7):
for i4 in range(i3+1,7):
for i5 in range(i4+1,7):
print i1,i2,i3,i4,i5

0 1 2 3 4
0 1 2 3 5
0 1 2 3 6
0 1 2 4 5
0 1 2 4 6
0 1 2 5 6
0 1 3 4 5
0 1 3 4 6
0 1 3 5 6
0 1 4 5 6
0 2 3 4 5
0 2 3 4 6
0 2 3 5 6
0 2 4 5 6
0 3 4 5 6
1 2 3 4 5
1 2 3 4 6
1 2 3 5 6
1 2 4 5 6
1 3 4 5 6
2 3 4 5 6

Have fun
Michael

Michael Amrhein
Guest
Posts: n/a

 01-25-2006
Michael Amrhein schrieb:
> Frode Ĝijord schrieb:
>> 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.
>>
>>
>>
>> ------------------------------------------------------------------------
>>
>> import sys
>> from timeit import Timer
>>
>> 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
>>
>>
>> def test():
>> cards = range(52)
>> for hand in comb(cards, 5):
>> "do something with the hand"
>> def main(argv):
>> t = Timer("test()", "from __main__ import test")
>> print t.timeit(1)
>>
>>
>> if __name__=="__main__":
>> sys.exit(main(sys.argv[1:]))

>
> If you don't need the flexibility of having the number of elements in
> your permutation as a parameter - as it seems to be the case in your
> poker example - simply use nested for-loops, 5 in this case.
> Example for 5 out of 7 (just to keep the output shorter):
> for i1 in range(7):
> for i2 in range(i1+1,7):
> for i3 in range(i2+1,7):
> for i4 in range(i3+1,7):
> for i5 in range(i4+1,7):
> print i1,i2,i3,i4,i5
>
> 0 1 2 3 4
> 0 1 2 3 5
> 0 1 2 3 6
> 0 1 2 4 5
> 0 1 2 4 6
> 0 1 2 5 6
> 0 1 3 4 5
> 0 1 3 4 6
> 0 1 3 5 6
> 0 1 4 5 6
> 0 2 3 4 5
> 0 2 3 4 6
> 0 2 3 5 6
> 0 2 4 5 6
> 0 3 4 5 6
> 1 2 3 4 5
> 1 2 3 4 6
> 1 2 3 5 6
> 1 2 4 5 6
> 1 3 4 5 6
> 2 3 4 5 6
>
> Have fun
> Michael

Even faster:
>>>[(i1,i2,i3,i4,i5) for i1 in range(7) for i2 in range(i1+1,7) for i3

in range(i2+1,7) for i4 in range(i3+1,7) for i5 in range(i4+1,7)]
[(0, 1, 2, 3, 4), (0, 1, 2, 3, 5), (0, 1, 2, 3, 6), (0, 1, 2, 4, 5), (0,
1, 2, 4, 6), (0, 1, 2, 5, 6), (0, 1, 3, 4, 5), (0, 1, 3, 4, 6), (0, 1,
3, 5, 6), (0, 1, 4, 5, 6), (0, 2, 3, 4, 5), (0, 2, 3, 4, 6), (0, 2, 3,
5, 6), (0, 2, 4, 5, 6), (0, 3, 4, 5, 6), (1, 2, 3, 4, 5), (1, 2, 3, 4,
6), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6)]
Michael

=?ISO-8859-1?Q?Frode_=D8ijord?=
Guest
Posts: n/a

 01-25-2006
Jack Diederich wrote:

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

Nah, evaluating the poker hands is the FUN part! I want to do that myself

> 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.

This is *exactly* what i wanted! I just installed it and the hand
generation is down to around 1.2 seconds now, and that I can live with
Now I just have to reduce the running time of the actual hand
evaluation with an order of magnitude...

Thanks!

--
Frode, SIM

"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand"

=?ISO-8859-1?Q?Frode_=D8ijord?=
Guest
Posts: n/a

 01-25-2006
Jack Diederich wrote:

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

Nah, evaluating the poker hands is the FUN part! I want to do that myself

> 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.

This is *exactly* what i wanted! I just installed it and the hand
generation is down to around 1.2 seconds now, and that I can live with
Now I just have to reduce the running time of the actual hand
evaluation with an order of magnitude...

Thanks!

--
Frode, SIM

"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand"

Terry Reedy
Guest
Posts: n/a

 01-25-2006

"Frode Ĝijord" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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.

The set of all possible 5-card poker hands is a constant. It appears you
need it over and over. But it is not clear to me whether you only need a
generator to iterate over the set or the whole set at once. If the latter,
one option is to generate it once, save to disk, and read it in. I'd try
both marshal and cpickle modules for read-in time.

Terry J. Reedy

Paul Rubin
Guest
Posts: n/a

 01-25-2006
Frode Ĝijord <(E-Mail Removed)> writes:
> > 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.

>
> This is *exactly* what i wanted! I just installed it and the hand
> generation is down to around 1.2 seconds now, and that I can live with

Note that you're looking at 24x more hands than you really need to,
since poker hand evaluation doesn't change if you re-label the four
suits. It's not like bridge, where spades beat hearts and so forth.

Paul Rubin
Guest
Posts: n/a

 01-25-2006
Paul Rubin <http://(E-Mail Removed)> writes:
> Note that you're looking at 24x more hands than you really need to,

Well, maybe not 24x. The exact number is more complicated. I'm still
too sleepy to figure this out right now but may think about it later.

Paul Rubin
Guest
Posts: n/a

 01-25-2006
Paul Rubin <http://(E-Mail Removed)> writes:
> Well, maybe not 24x. The exact number is more complicated. I'm still
> too sleepy to figure this out right now but may think about it later.

Turns out to be 7x, for reasons that are a bit mysterious.
Ignoring suits, think of the 5-card hand as a 5-digit number base 13.
There are 13**5 such numbers, but 13 of them are impossible as 5-card
deals (all 5 digits are the same, "5 of a kind"). That leaves
13**5-13 = 371280, which is 1/7th of C(52,5). Can someone give
a combinatorial explanation?

Generating the hands is simple:

def deals():
for i in xrange(13**5):
cards = [(i//p) % 13 for p in (1, 13, 169, 2197, 28561)]
yield cards

The funny numbers in that list are the first four powers of 13.
Flattening the generator with list() takes about 8 sec on my p3-750.
Unrolling the list comprehension and making tuples instead of lists,
cards = (i%13, (i//13)%13, (i//169)%13, (i//2197)%13, (i//28561)%13)
speeds it up to 5.6 seconds.

In categorizing the hands from this generator, you have to:

- discard the hands that are 5-of-a-kind (there are 13 of them)

- in hands where all 5 numbers are distinct, consider whether
the hand might be a flush (probability is 1 in 256).