Fast generation of permutations

[Michael Amrhein]

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