[Numpy-discussion] how do I list all combinations
Zachary Pincus
zpincus at stanford.edu
Wed Dec 26 18:23:40 EST 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 at scipy.org
> http://projects.scipy.org/mailman/listinfo/numpy-discussion
More information about the NumPy-Discussion
mailing list