Hi I've been looking at "fromfunction" and itertools but I'm flummoxed. I have an arbitrary number of lists. I want to form all possible combinations from all lists. So if r1=["dog","cat"] r2=[1,2] I want to return [["dog",1],["dog",2],["cat",1],["cat",2]] It's obvious when the number of lists is not arbitrary. But what if thats not known until runtime? Mathew
On Dec 26, 2007 12:22 PM, Mathew Yeates <myeates@jpl.nasa.gov> wrote:
I have an arbitrary number of lists. I want to form all possible combinations from all lists. So if r1=["dog","cat"] r2=[1,2]
I want to return [["dog",1],["dog",2],["cat",1],["cat",2]]
It's obvious when the number of lists is not arbitrary. But what if thats not known until runtime?
Would this work? Make a function that takes two inputs (a list of lists and a list) and returns a list of lists that contains all possible combinations. Iterate through all lists by calling the function with the output of the previous call (a list of lists) and the next list.
Hi --
I have an arbitrary number of lists. I want to form all possible combinations from all lists. So if r1=["dog","cat"] r2=[1,2]
I want to return [["dog",1],["dog",2],["cat",1],["cat",2]]
Try this: In [25]: [(x, y) for x in r1 for y in r2] Out[25]: [('dog', 1), ('dog', 2), ('cat', 1), ('cat', 2)] Cheers, Stuart Brorson Interactive Supercomputing, inc. 135 Beaver Street | Waltham | MA | 02452 | USA http://www.interactivesupercomputing.com/
yes, I came up with this and may use it. Seems like it would be insanely slow but my problem is small enough that it might be okay. Thanks Keith Goodman wrote:
On Dec 26, 2007 12:22 PM, Mathew Yeates <myeates@jpl.nasa.gov> wrote:
I have an arbitrary number of lists. I want to form all possible combinations from all lists. So if r1=["dog","cat"] r2=[1,2]
I want to return [["dog",1],["dog",2],["cat",1],["cat",2]]
It's obvious when the number of lists is not arbitrary. But what if thats not known until runtime?
Would this work?
Make a function that takes two inputs (a list of lists and a list) and returns a list of lists that contains all possible combinations. Iterate through all lists by calling the function with the output of the previous call (a list of lists) and the next list. _______________________________________________ Numpy-discussion mailing list Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
On Dec 26, 2007 1:45 PM, Keith Goodman <kwgoodman@gmail.com> wrote:
On Dec 26, 2007 12:22 PM, Mathew Yeates <myeates@jpl.nasa.gov> wrote:
I have an arbitrary number of lists. I want to form all possible combinations from all lists. So if r1=["dog","cat"] r2=[1,2]
I want to return [["dog",1],["dog",2],["cat",1],["cat",2]]
It's obvious when the number of lists is not arbitrary. But what if thats not known until runtime?
Would this work?
Make a function that takes two inputs (a list of lists and a list) and returns a list of lists that contains all possible combinations. Iterate through all lists by calling the function with the output of the previous call (a list of lists) and the next list. ____
Yeah, you can do it with recursion, but I don't think it would be quite as efficient. An example of the explicit approach, define the following generator: def count(listoflists) : counter = [i[0] for i in listoflists] maxdigit = [len(i) - 1 for i in listoflists] 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 In [30]: a = ['dog', 'cat', 'horse'] In [31]: b = ['red', 'black'] In [32]: c = [a,b] In [33]: for i in count.count(c) : print [c[j][i[j]] for j in range(len(c))] ....: ['dog', 'red'] ['cat', 'red'] ['horse', 'red'] ['dog', 'black'] ['cat', 'black'] ['horse', 'black'] ___________________________________________
Numpy-discussion mailing list Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
On Dec 26, 2007 2:30 PM, Charles R Harris <charlesr.harris@gmail.com> wrote:
On Dec 26, 2007 1:45 PM, Keith Goodman <kwgoodman@gmail.com> wrote:
On Dec 26, 2007 12:22 PM, Mathew Yeates <myeates@jpl.nasa.gov> wrote:
I have an arbitrary number of lists. I want to form all possible combinations from all lists. So if r1=["dog","cat"] r2=[1,2]
I want to return [["dog",1],["dog",2],["cat",1],["cat",2]]
It's obvious when the number of lists is not arbitrary. But what if thats not known until runtime?
Would this work?
Make a function that takes two inputs (a list of lists and a list) and returns a list of lists that contains all possible combinations. Iterate through all lists by calling the function with the output of the previous call (a list of lists) and the next list. ____
Yeah, you can do it with recursion, but I don't think it would be quite as efficient. An example of the explicit approach, define the following generator:
def count(listoflists) : counter = [i[0] for i in listoflists]
Make that counter = [0 for i in listoflists]. That bug slipped in going from [0]*len(listoflists). Chuck
Thanks Chuck. Charles R Harris wrote:
On Dec 26, 2007 2:30 PM, Charles R Harris <charlesr.harris@gmail.com <mailto:charlesr.harris@gmail.com>> wrote:
On Dec 26, 2007 1:45 PM, Keith Goodman <kwgoodman@gmail.com <mailto:kwgoodman@gmail.com>> wrote:
On Dec 26, 2007 12:22 PM, Mathew Yeates <myeates@jpl.nasa.gov <mailto:myeates@jpl.nasa.gov>> wrote: > I have an arbitrary number of lists. I want to form all possible > combinations from all lists. So if > r1=["dog","cat"] > r2=[1,2] > > I want to return [["dog",1],["dog",2],["cat",1],["cat",2]] > > It's obvious when the number of lists is not arbitrary. But what if > thats not known until runtime?
Would this work?
Make a function that takes two inputs (a list of lists and a list) and returns a list of lists that contains all possible combinations. Iterate through all lists by calling the function with the output of the previous call (a list of lists) and the next list. ____
Yeah, you can do it with recursion, but I don't think it would be quite as efficient. An example of the explicit approach, define the following generator:
def count(listoflists) : counter = [i[0] for i in listoflists]
Make that counter = [0 for i in listoflists]. That bug slipped in going from [0]*len(listoflists).
Chuck
------------------------------------------------------------------------
_______________________________________________ Numpy-discussion mailing list Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
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
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
On Dec 26, 2007 1:22 PM, Mathew Yeates <myeates@jpl.nasa.gov> wrote:
Hi I've been looking at "fromfunction" and itertools but I'm flummoxed.
I have an arbitrary number of lists. I want to form all possible combinations from all lists. So if r1=["dog","cat"] r2=[1,2]
I want to return [["dog",1],["dog",2],["cat",1],["cat",2]]
It's obvious when the number of lists is not arbitrary. But what if thats not known until runtime?
It's a mixed radix counter. Emulate the usual add and carry with a list of digits using the length of the corresponding list as the radix at that position. Sorta like an abacus, but with different numbers of beads in each position. Chuck
Le Mercredi 26 Décembre 2007 21:22, Mathew Yeates a écrit :
Hi I've been looking at "fromfunction" and itertools but I'm flummoxed.
I have an arbitrary number of lists. I want to form all possible combinations from all lists. So if r1=["dog","cat"] r2=[1,2]
I want to return [["dog",1],["dog",2],["cat",1],["cat",2]]
It's obvious when the number of lists is not arbitrary. But what if thats not known until runtime?
Mathew
In the 'Reference Manual' of Python there is an example.
_______________________________________________ Numpy-discussion mailing list Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
-- René Bastian http://www.musiques-rb.org http://pythoneon.musiques-rb.org http://divergences.be édition du 15.11.07 : musique
Which reference manual? René Bastian wrote:
Le Mercredi 26 Décembre 2007 21:22, Mathew Yeates a écrit :
Hi I've been looking at "fromfunction" and itertools but I'm flummoxed.
I have an arbitrary number of lists. I want to form all possible combinations from all lists. So if r1=["dog","cat"] r2=[1,2]
I want to return [["dog",1],["dog",2],["cat",1],["cat",2]]
It's obvious when the number of lists is not arbitrary. But what if thats not known until runtime?
Mathew
In the 'Reference Manual' of Python there is an example.
_______________________________________________ Numpy-discussion mailing list Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
On Wed, 26 Dec 2007, Mathew Yeates apparently wrote:
r1=["dog","cat"] r2=[1,2] I want to return [["dog",1],["dog",2],["cat",1],["cat",2]]
This is a Cartesian product. Sage has ``cartesian_product_iterator`` for this. Also <URL:http://www.sagemath.org/doc/html/ref/module-sage.combinat.cartesian-product....> Here is a Cookbook implementation. <URL:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/302478> The generator may be adequate to your needs. Here is a recursive implementation that does not use multi-dimensional indexing: def set_product(*sets): last_set = sets[-1] drop_last = sets[:-1] if drop_last: result = set( x+(y,) for x in set_product(*drop_last) for y in last_set ) else: result = set( (y,) for y in last_set ) return result Sorry for a late reply. I'm catching up on email... Cheers, Alan Isaac
participants (8)
-
Alan G Isaac -
Charles R Harris -
Keith Goodman -
Mathew Yeates -
René Bastian -
Stuart Brorson -
Timothy Hochberg -
Zachary Pincus