# Fast generation of permutations

Wed Jan 25 11:51:51 EST 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

```