Re: [Numpy-discussion] how do I list all combinations

[Alan G Isaac]

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 
http://www.sagemath.org/doc/html/ref/module-sage.combinat.cartesian-product.html>

Here is a Cookbook implementation.
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



___
Numpy-discussion mailing list
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion

Re: [Numpy-discussion] how do I list all combinations

[Zachary Pincus]

Hi all,

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

> In: numpy.ndindex?
> Type:   type
> Base Class: 
> String Form:
> 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

___
Numpy-discussion mailing list
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion

Re: [Numpy-discussion] how do I list all combinations

[Timothy Hochberg]

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

Re: [Numpy-discussion] how do I list all combinations

[Mathew Yeates]

Thanks Chuck.

Charles R Harris wrote:
>
>
> On Dec 26, 2007 2:30 PM, Charles R Harris <[EMAIL PROTECTED] 
> > wrote:
>
>
>
> On Dec 26, 2007 1:45 PM, Keith Goodman <[EMAIL PROTECTED]
> > wrote:
>
> On Dec 26, 2007 12:22 PM, Mathew Yeates <[EMAIL PROTECTED]
> > 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
>   


___
Numpy-discussion mailing list
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion

Re: [Numpy-discussion] how do I list all combinations

[Charles R Harris]

On Dec 26, 2007 2:30 PM, Charles R Harris <[EMAIL PROTECTED]> wrote:

>
>
> On Dec 26, 2007 1:45 PM, Keith Goodman <[EMAIL PROTECTED]> wrote:
>
> > On Dec 26, 2007 12:22 PM, Mathew Yeates <[EMAIL PROTECTED]> 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

Re: [Numpy-discussion] how do I list all combinations

[Charles R Harris]

On Dec 26, 2007 1:45 PM, Keith Goodman <[EMAIL PROTECTED]> wrote:

> On Dec 26, 2007 12:22 PM, Mathew Yeates <[EMAIL PROTECTED]> 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
>
___
Numpy-discussion mailing list
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion

Re: [Numpy-discussion] how do I list all combinations

[Mathew Yeates]

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
>> 
>
>   


___
Numpy-discussion mailing list
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion

Re: [Numpy-discussion] how do I list all combinations

[Mathew Yeates]

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 <[EMAIL PROTECTED]> 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
>
>   


___
Numpy-discussion mailing list
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion

Re: [Numpy-discussion] how do I list all combinations

[Stuart Brorson]

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/
___
Numpy-discussion mailing list
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion

Re: [Numpy-discussion] how do I list all combinations

[René Bastian]

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


___
Numpy-discussion mailing list
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion

Re: [Numpy-discussion] how do I list all combinations

[Charles R Harris]

On Dec 26, 2007 1:22 PM, Mathew Yeates <[EMAIL PROTECTED]> 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
___
Numpy-discussion mailing list
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion

Re: [Numpy-discussion] how do I list all combinations

[Keith Goodman]

On Dec 26, 2007 12:22 PM, Mathew Yeates <[EMAIL PROTECTED]> 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

[Numpy-discussion] how do I list all combinations

[Mathew Yeates]

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


___
Numpy-discussion mailing list
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion