Fast generation of permutations

[Michael Amrhein]

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