[Numpy-discussion] how do I list all combinations

Zachary Pincus zpincus@stanford....
Wed Dec 26 17:23:40 CST 2007


Hi all,

I use numpy's own ndindex() for tasks like these:

> In: numpy.ndindex?
> Type:           type
> Base Class:     <type 'type'>
> String Form:    <class 'numpy.lib.index_tricks.ndindex'>
> Namespace:      Interactive
> File:           /Library/Frameworks/Python.framework/Versions/2.4/ 
> lib/python2.4/site-packages/numpy/lib/index_tricks.py
> Docstring:
>     Pass in a sequence of integers corresponding
>     to the number of dimensions in the counter.  This iterator
>     will then return an N-dimensional counter.
>
>     Example:
>     >>> for index in ndindex(3,2,1):
>     ...     print index
>     (0, 0, 0)
>     (0, 1, 0)
>     (1, 0, 0)
>     (1, 1, 0)
>     (2, 0, 0)
>     (2, 1, 0)

Here's a combination function using numpy.ndindex:

def combinations(*lists):
   lens = [len(l) for l in lists]
   for indices in numpy.ndindex(*lens):
     yield [l[i] for l, i in zip(lists, indices)]

r1=["dog","cat"]
r2=[1,2]
list(combinations(r1, r2))

Out: [['dog', 1], ['dog', 2], ['cat', 1], ['cat', 2]]

Or you could use 'map' and 'operator.getitem', which might be faster(?):
def combinations(*lists):
   lens = [len(l) for l in lists]
   for indices in numpy.ndindex(*lens):
     yield map(operator.getitem, lists, indices)


In the python cookbook, there are numerous similar recipes for  
generating permutations, combinations, and the like.


Zach Pincus

Program in Biomedical Informatics and Department of Biochemistry
Stanford University School of Medicine




On Dec 26, 2007, at 5:48 PM, Timothy Hochberg wrote:

>
> Here's a baroque way to do it using generated code:
>
>     def cg_combinations(seqs):
>         n = len(seqs)
>         chunks = ["def f(%s):" % ', '.join('s%s' % i for i in range 
> (n))]
>         for i in reversed(range(n)):
>             chunks.append(" " * (n -i) + "for x%s in s%s:" % (i, i))
>         chunks.append(" " * n + " yield (" + ', '.join('x%s' % i  
> for i in range(n)) + ')')
>         code = '\n'.join(chunks)
>         exec code
>         return f(*seqs)
>
> It should be reasonably fast, if non-obvious. I've included a  
> version with some timing and testing against Chucks version below.  
> Enjoy.
>
> (Also, it can be simplified slightly, but I wanted to generate in  
> the same order as Chuck for comparison purposes).
>
>
> ======================================================================
>
>
>     def count(seqs) :
>         counter = [0 for i in seqs]
>         maxdigit = [len(i) - 1 for i in seqs]
>         yield counter
>         while True :
>             i = 0;
>             while i < len(counter) and counter[i] >= maxdigit[i] :
>                 counter[i] = 0
>                 i += 1
>             if i < len(counter) :
>                 counter[i] += 1
>                 yield counter
>             else :
>                 return
>
>     def count_combinations(seqs):
>         for c in count(seqs):
>             yield tuple(s[i] for (s, i) in zip(seqs, c))
>
>     def cg_combinations(seqs):
>         n = len(seqs)
>         chunks = ["def f(%s):" % ', '.join('s%s' % i for i in range 
> (n))]
>         for i in reversed(range(n)):
>             chunks.append(" " * (n -i) + "for x%s in s%s:" % (i, i))
>         chunks.append(" " * n + " yield (" + ', '.join('x%s' % i  
> for i in range(n)) + ')')
>         code = '\n'.join(chunks)
>         exec code
>         return f(*seqs)
>
>     a = "abcde"*10
>     b = range(99)
>     c = [x**2 for x in range(33)]
>     seqs = [a, b, c]
>
>     if __name__ == "__main__":
>         assert list(count_combinations(seqs)) == list 
> (cg_combinations(seqs))
>
>         import timeit
>         test = timeit.Timer('list(count_combinations(seqs))',
>                'from __main__ import count_combinations, seqs')
>         t1 = test.timeit(number=10)
>         test = timeit.Timer('list(cg_combinations(seqs))',
>                'from __main__ import cg_combinations, seqs')
>         t2 = test.timeit(number=10)
>         print t1, t2
> _______________________________________________
> Numpy-discussion mailing list
> Numpy-discussion@scipy.org
> http://projects.scipy.org/mailman/listinfo/numpy-discussion



More information about the Numpy-discussion mailing list