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
--
http://mail.python.org/mailman/listinfo/python-list
