Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

7 views

Skip to first unread message

Jan 25, 2006, 9:33:48 AM1/25/06

to

Hi all,

given a sequence of n elements i need to generate all possible

permutations of length k <= n.

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"

Jan 25, 2006, 11:22:40 AM1/25/06

to pytho...@python.org

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.

>

> 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

Jan 25, 2006, 11:51:51 AM1/25/06

to fr...@sim.no

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:]))

> 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

>

>

> 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

Jan 25, 2006, 12:03:35 PM1/25/06

to fr...@sim.no

Michael Amrhein schrieb: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

>>>[(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

Jan 25, 2006, 12:18:51 PM1/25/06

to pytho...@python.org

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!

Jan 25, 2006, 12:26:43 PM1/25/06

to pytho...@python.org

"Frode Řijord" <fr...@sim.no> wrote in message

news:11tf35q...@corp.supernews.com...

> 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

Jan 25, 2006, 12:18:51 PM1/25/06

to Jack Diederich, pytho...@python.org

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!

--

Jan 25, 2006, 1:03:09 PM1/25/06

to

Frode Øijord <fr...@sim.no> 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 :)

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

Jan 25, 2006, 1:07:07 PM1/25/06

to

Paul Rubin <http://phr...@NOSPAM.invalid> writes:

> Note that you're looking at 24x more hands than you really need to,

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

Jan 25, 2006, 4:39:24 PM1/25/06

to

Paul Rubin <http://phr...@NOSPAM.invalid> 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.

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

Jan 28, 2006, 5:03:13 AM1/28/06

to

Paul Rubin wrote:

> def deals():

> for i in xrange(13**5):

> cards = [(i//p) % 13 for p in (1, 13, 169, 2197, 28561)]

> yield cards

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__=='__main__':

test()

Jan 28, 2006, 11:07:34 AM1/28/06

to

"Anton Vredegoor" <anton.v...@gmail.com> writes:

> > def deals():

> > for i in xrange(13**5):

> > cards = [(i//p) % 13 for p in (1, 13, 169, 2197, 28561)]

> > yield cards

>

> This gives hands like [0,0,0,0,1] and [0,0,0,1,0] which are

> permutations of one another.

> > def deals():

> > for i in xrange(13**5):

> > cards = [(i//p) % 13 for p in (1, 13, 169, 2197, 28561)]

> > yield cards

>

> This gives hands like [0,0,0,0,1] and [0,0,0,1,0] which are

> permutations of one another.

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.

> Below is a piece of code that avoids this.

Nice.

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

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.

Jan 29, 2006, 9:37:27 AM1/29/06

to

Paul Rubin wrote:

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

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

Jan 29, 2006, 9:48:12 AM1/29/06

to

Anton Vredegoor wrote:

> Paul Rubin wrote:

>

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

>

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

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

that.

Anton

0 new messages

Search

Clear search

Close search

Google apps

Main menu