Fast generation of permutations

[Frode Øijord]

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(item s)):
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(item s)):
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__=="__ma in__":
sys.exit(main(s ys.argv[1:]))

[Jack Diederich]

Re: Fast generation of permutations

On Wed, Jan 25, 2006 at 03:33:48PM +0100, Frode ?ijord wrote:[color=blue]
> 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(item s)):
> 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.
>[/color]

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.Combin ation(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]

Re: Fast generation of permutations

Frode Øijord schrieb:[color=blue]
> 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(item s)):
> 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(item s)):
> 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__=="__ma in__":
> sys.exit(main(s ys.argv[1:]))[/color]

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]

Re: Fast generation of permutations

Michael Amrhein schrieb:[color=blue]
> Frode Øijord schrieb:[color=green]
>> 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(item s)):
>> 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(item s)):
>> 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__=="__ma in__":
>> sys.exit(main(s ys.argv[1:]))[/color]
>
> 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[/color]
Even faster:[color=blue][color=green][color=darkred]
>>>[(i1,i2,i3,i4,i5 ) for i1 in range(7) for i2 in range(i1+1,7) for i3[/color][/color][/color]
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

[Frode Øijord]

Re: Fast generation of permutations

Jack Diederich wrote:
[color=blue]
> You might want to look at a specific purpose library for poker hands:
> http://pokersource.sourceforge.net/[/color]

Nah, evaluating the poker hands is the FUN part! I want to do that myself :)
[color=blue]
> 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.Combin ation(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.[/color]

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]

Re: Fast generation of permutations


"Frode Øijord" <frodo@sim.no > wrote in message
news:11tf35qjfe luka1@corp.supe rnews.com...[color=blue]
> 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.[/color]

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

[Frode Øijord]

Re: Fast generation of permutations

Jack Diederich wrote:
[color=blue]
> You might want to look at a specific purpose library for poker hands:
> http://pokersource.sourceforge.net/[/color]

Nah, evaluating the poker hands is the FUN part! I want to do that myself :)
[color=blue]
> 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.Combin ation(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.[/color]

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"

[Paul Rubin]

Re: Fast generation of permutations

Frode Øijord <frodo@sim.no > writes:[color=blue][color=green]
> > cards = range(52)
> > for (hand) in probstat.Combin ation(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.[/color]
>
> 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 :)[/color]

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]

Re: Fast generation of permutations

Paul Rubin <http://phr.cx@NOSPAM.i nvalid> writes:[color=blue]
> Note that you're looking at 24x more hands than you really need to,[/color]

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]

Re: Fast generation of permutations

Paul Rubin <http://phr.cx@NOSPAM.i nvalid> writes:[color=blue]
> 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.[/color]

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

[Anton Vredegoor]

Re: Fast generation of permutations

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

This gives hands like [0,0,0,0,1] and [0,0,0,1,0] which are
permutations of one another.

Below is a piece of code that avoids this. Here's how to interprete its
output. Suppose one gets a hand like [0,1,2,3,4]. This means that it
would be possible to create 1024 (4**5) poker hands from this, by
"coloring" the cards.

Another hand, for example [0,0,1,2,3], would allow only 384 colorings,
because the two zeros would contribute choose 2 out of 4 (colors), so 6
colorings. The other numbers remain available for 4 colorings, which
gives 6*4**3 (==384) colorings for this hand.

Similar things happen for other partionings of the hands into numbers.
In fact I am now investigating a description based on integer
partitions of the number 5. I am not sure whether I want to partition
based on colors or on numbers, that seems to arbitrary.

This is very fascinating. Maybe someday I'll make a tkinter script with
a visual tree structure allowing all kinds of numbers of "cards", and
arbitrary numbers of variables to partition by.

This would then give result sets like those strange quantum particles,
such as quarks.

Have fun,

Anton

def hands(L = [0]):
if len(L) == 6:
if L[1] != L[-1]: #no five of a kind
yield L[1:]
else:
for i in range(L[-1],13):
for H in hands(L+[i]):
yield H

def pprint(i,hand):
print '%5i: ' %i,
for x in hand:
print '%2i ' % x,
print

def test():
H = hands()
total = 0
for i,x in enumerate(H):
pprint(i,x)

if __name__=='__ma in__':
test()

[Paul Rubin]

Re: Fast generation of permutations

"Anton Vredegoor" <anton.vredegoo r@gmail.com> writes:[color=blue][color=green]
> > def deals():
> > for i in xrange(13**5):
> > cards = [(i//p) % 13 for p in (1, 13, 169, 2197, 28561)]
> > yield cards[/color]
>
> This gives hands like [0,0,0,0,1] and [0,0,0,1,0] which are
> permutations of one another.[/color]

Yes, that's intentional, I thought the idea was to figure out the
probability of each type of poker hand, which means you have to
count those multiple occurrences.
[color=blue]
> Below is a piece of code that avoids this.[/color]

Nice.
[color=blue]
> Another hand, for example [0,0,1,2,3], would allow only 384 colorings,...
> Similar things happen for other partionings of the hands into numbers...
>
> This is very fascinating. Maybe someday I'll make a tkinter script with
> a visual tree structure allowing all kinds of numbers of "cards", and
> arbitrary numbers of variables to partition by.[/color]

Cool, I'd still like to know why (13**5)-13 = C(52,5) other than
by just doing the arithmetic and comparing the results. Maybe your
tkinter script can show that.

[Anton Vredegoor]

Re: Fast generation of permutations

Paul Rubin wrote:
[color=blue]
> Cool, I'd still like to know why (13**5)-13 = C(52,5) other than
> by just doing the arithmetic and comparing the results. Maybe your
> tkinter script can show that.[/color]

That seems to be very hard :-) Unless I'm missing something.

Anton

def noverk(n,k):
return reduce(lambda a,b: a*(n-b)/(b+1),range(k), 1)

print noverk(52,5)
print 13**5-13

#prints:

2598960
371280

[Anton Vredegoor]

Re: Fast generation of permutations

Anton Vredegoor wrote:
[color=blue]
> Paul Rubin wrote:
>[color=green]
> > Cool, I'd still like to know why (13**5)-13 = C(52,5) other than
> > by just doing the arithmetic and comparing the results. Maybe your
> > tkinter script can show that.[/color]
>
> That seems to be very hard :-) Unless I'm missing something.[/color]

Like a factor seven, you mentioned that a few posts back. Sorry about
that.

Anton