Pulling all n-sized combinations from a list

[Michael Spencer]

Swroteb wrote:
> Paul Rubin wrote:
>> I think the natural approach is to make a generator that yields a
>> 5-tuple for each combination, and then have your application iterate
>> over that generator.  Here's my version:
>>
>>     def comb(x,n):
>>         """Generate combinations of n items from list x"""
>>         if n==0:
>>             yield []
>>             return
>>         for i in xrange(len(x)-n+1):
>>             for r in comb(x[i+1:], n-1):
>>                 yield [x[i]] + r
>>
>>     for c in comb([1,2,3,4,5], 3):
>>         print c
>>
>> The output is:
>>     >>>
>>     [1, 2, 3]
>>     [1, 2, 4]
>>     [1, 2, 5]
>>     [1, 3, 4]
>>     [1, 3, 5]
>>     [1, 4, 5]
>>     [2, 3, 4]
>>     [2, 3, 5]
>>     [2, 4, 5]
>>     [3, 4, 5]
>>     >>>
> 
> Ah, this definitely seems to work!  It's a lot nicer in appearance than
> my previous code, that's for sure.  It actually runs in approximately
> the same amount of time though.  So, using your comb method, I have the
> following code now:
> 
>         myCombinations = comb(myList, 5)
>         for a, b, c, d, e in myCombinations:
>             # my code
> 
> myList is 48 elements in size, so I'm going to get 1712304
> combinations.  From what I can tell, my speed problems aren't in the
> list generation anymore.
> 
> Thanks for the assistance, Paul!  I appreciate it.  :)
> 
If you're concerned about speed, and don't mind lack of flexibility, spelling 
out the iteration within your function is much faster:

def comb(seq):
     indices = range(len(seq))
     for ia in indices:
         a = seq[ia]
         for ib in indices[ia+1:]:
             b = seq[ib]
             for ic in indices[ib+1:]:
                 c = seq[ic]
                 for id in indices[ic+1:]:
                     d = seq[id]
                     for ie in indices[id+1:]:
                         e = seq[ie]

This is roughly 30 times faster on my box than the general solution above

Michael