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:])) 13 2962
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
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 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
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"
"Frode Øijord" <fr***@sim.no> wrote in message
news:11*************@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
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"
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 :)
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 <http://ph****@NOSPAM.invalid> 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 <http://ph****@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.
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).
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()
"Anton Vredegoor" <an*************@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.
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.
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
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Steve Goldman |
last post by:
Hi,
I am trying to come up with a way to develop all n-length permutations of a
given list of values. The short function below seems to work, but I can't
help thinking there's a better way. ...
|
by: John Trunek |
last post by:
I have a set of X items, but want permutations of length Y (X > Y). I
am aware of the permutation functions in <algorithm>, but I don't
believe this will do what I want. Is there a way, either...
|
by: GS |
last post by:
The stdint.h header definition mentions five integer categories,
1) exact width, eg., int32_t
2) at least as wide as, eg., int_least32_t
3) as fast as possible but at least as wide as, eg.,...
|
by: onkar |
last post by:
How to generate different permutations of n char array?
ex : for n= 3, and basic string = abc
bca
cab
bac
cab
.....
...
..
|
by: anurag |
last post by:
hey can anyone help me in writing a code in c (function) that prints
all permutations of a string.please help
|
by: Christian Meesters |
last post by:
Hi,
I'd like to hack a function which returns all possible permutations as lists
(or tuples) of two from a given list. So far, I came up with this solution,
but it turned out to be too slow for...
|
by: JosAH |
last post by:
Greetings,
last week we talked a bit about generating permutations and I told you that
this week will be about combinations. Not true; there's a bit more to tell
about permutations and that's...
|
by: Shraddha |
last post by:
Suppose we are having 3 variables...a,b,c
And we want to print the permutations of these variables...Such
as...abc,acb,bca...all 6 of them...
But we are not supposed to do it mannually...
I...
|
by: Bill Cunningham |
last post by:
I don't know if I'll need pointers for this or not. I wants numbers
10^16. Like a credit card 16 digits of possible 10 numbers, so I guess that
would be 10^16. So I have
int num ;
These are of...
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
|
by: ryjfgjl |
last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
| |