I was thinking about a problem I had: suppose I have a list of possible values. I want to to have a list of all possible lists of length n whose values are in that original list.
For example: if my values are ['a', 'b', 'c'], then all possible lists of length 2 would be: aa, ab, ac, ba, bb, bc, ca, cb, cc.
I created a recursive program to do it, but I was wondering if there was a better way of doing it (possibly with list comprehensions).
Here's my recursive version:
vals = ['a', 'b', 'c']
def foo(length): if length <=0: return [] if length == 1: return [[x] for x in vals] else: return [x + [y] for x in foo(length - 1) for y in vals]
> For example: if my values are ['a', 'b', 'c'], then all possible lists > of length 2 would be: aa, ab, ac, ba, bb, bc, ca, cb, cc.
> I created a recursive program to do it, but I was wondering if there > was a better way of doing it (possibly with list comprehensions).
> Here's my recursive version:
> vals = ['a', 'b', 'c']
> def foo(length): > if length <=0: > return [] > if length == 1: > return [[x] for x in vals] > else: > return [x + [y] for x in foo(length - 1) for y in vals]
Sounds like you want one of the combinitoric generators found in itertools[1] -- in this case, the itertools.product() does what you describe. According to the docs, it was added in 2.6 so if you're running an older version, you'd have to back-port it.
> For example: if my values are ['a', 'b', 'c'], then all possible lists > of length 2 would be: aa, ab, ac, ba, bb, bc, ca, cb, cc. >>> from itertools import product >>> list(product("abc", repeat=2))
>> For example: if my values are ['a', 'b', 'c'], then all possible lists >> of length 2 would be: aa, ab, ac, ba, bb, bc, ca, cb, cc.
>> I created a recursive program to do it, but I was wondering if there >> was a better way of doing it (possibly with list comprehensions).
>> Here's my recursive version:
>> vals = ['a', 'b', 'c']
>> def foo(length): >> if length <=0: >> return [] >> if length == 1: >> return [[x] for x in vals] >> else: >> return [x + [y] for x in foo(length - 1) for y in vals]
> Sounds like you want one of the combinitoric generators found in > itertools[1] -- in this case, the itertools.product() does what you > describe. According to the docs, it was added in 2.6 so if you're > running an older version, you'd have to back-port it
Or on systems with list comps try:
>>> V='abc' >>> ['%s%s'%(ii,jj) for ii in V for jj in V] ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc'] >>>
On Mon, Jul 13, 2009 at 1:58 PM, Emile van Sebille<em...@fenx.com> wrote: > On 7/13/2009 9:33 AM Tim Chase said...
>>> For example: if my values are ['a', 'b', 'c'], then all possible lists >>> of length 2 would be: aa, ab, ac, ba, bb, bc, ca, cb, cc.
>>> I created a recursive program to do it, but I was wondering if there >>> was a better way of doing it (possibly with list comprehensions).
>>> Here's my recursive version:
>>> vals = ['a', 'b', 'c']
>>> def foo(length): >>> if length <=0: >>> return [] >>> if length == 1: >>> return [[x] for x in vals] >>> else: >>> return [x + [y] for x in foo(length - 1) for y in vals]
>> Sounds like you want one of the combinitoric generators found in >> itertools[1] -- in this case, the itertools.product() does what you >> describe. According to the docs, it was added in 2.6 so if you're running >> an older version, you'd have to back-port it
>>>> a = "abc" >>>> [(x, y) for x in a for y in a] > [('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'b'), ('b', 'c'), > ('c', 'a'), ('c', 'b'), ('c', 'c')]
> But I like bearophile's version better.
Andreas,
Thanks, but I think you were missing my point. I should have explained better.
The advantage that bearophile's version is generic with respect to the number of elements in each combination. To go from 2 element pairs (e.g. ('a', 'c')) to 5 element pairs (e.g. ('a', 'c', 'b', 'b', 'e')) requires only a change in a parameter passed to itertools.
I don't see how you would do that with list comprehensions. You're example works nicely with 2 element pairs, but it seems to me like you'd need to recode it if you wanted to change it to 5 element pairs.
Am I wrong about that? Can you think of a way to write a function that, using list comprehensions, takes a list of values and the size of each combination, and returns the len(list)**(combination size) possible combinations using those values?
> >>>> a = "abc" > >>>> [(x, y) for x in a for y in a] > > [('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'b'), ('b', 'c'), > > ('c', 'a'), ('c', 'b'), ('c', 'c')]
> > But I like bearophile's version better.
> Andreas,
> Thanks, but I think you were missing my point. I should have explained better.
> The advantage that bearophile's version is generic with respect to the > number of elements in each combination. To go from 2 element pairs > (e.g. ('a', 'c')) to 5 element pairs (e.g. ('a', 'c', 'b', 'b', 'e')) > requires only a change in a parameter passed to itertools.
> I don't see how you would do that with list comprehensions. You're > example works nicely with 2 element pairs, but it seems to me like > you'd need to recode it if you wanted to change it to 5 element pairs.
> Am I wrong about that? Can you think of a way to write a function > that, using list comprehensions, takes a list of values and the size > of each combination, and returns the len(list)**(combination size) > possible combinations using those values?
> Thanks again, > David
David,
I think my post got caught in the nebulous email eddys and seems to have taken 16 hours to arrive on the list. It was meant to be a reply to your first post, not your second.
Having said that, I think I missed the point of that post too ;o)
Maybe someone smarter than me can come up with a way to dynamically nest the fors in a list comprehension, but I certainly can't do it.
> > > Certainly possible with list comprehensions.
> > >>>> a = "abc" > > >>>> [(x, y) for x in a for y in a] > > > [('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'b'), ('b', > 'c'), > > > ('c', 'a'), ('c', 'b'), ('c', 'c')]
> > > But I like bearophile's version better.
> > Andreas,
> > Thanks, but I think you were missing my point. I should have explained > better.
> > The advantage that bearophile's version is generic with respect to the > > number of elements in each combination. To go from 2 element pairs > > (e.g. ('a', 'c')) to 5 element pairs (e.g. ('a', 'c', 'b', 'b', 'e')) > > requires only a change in a parameter passed to itertools.
> > I don't see how you would do that with list comprehensions. You're > > example works nicely with 2 element pairs, but it seems to me like > > you'd need to recode it if you wanted to change it to 5 element pairs.
> > Am I wrong about that? Can you think of a way to write a function > > that, using list comprehensions, takes a list of values and the size > > of each combination, and returns the len(list)**(combination size) > > possible combinations using those values?
> > Thanks again, > > David
> David,
> I think my post got caught in the nebulous email eddys and seems to have > taken 16 hours to arrive on the list. It was meant to be a reply to your > first post, not your second.
> Having said that, I think I missed the point of that post too ;o)
> Maybe someone smarter than me can come up with a way to dynamically nest > the fors in a list comprehension, but I certainly can't do it.
Well, I don't use list comprehension, but you can certainly make dynamic for loops. Not that this is a replacement for itertools (I wrote it before itertools had the ability to do all this).
def ooloop6(a, n, perm=True, repl=True): if (not repl) and (n>len(a)): return r0 = range(n) r1 = r0[1:] if perm and repl: # ok v = ','.join(['c%s' % i for i in r0]) f = ' '.join(['for c%s in a' % i for i in r0]) e = ''.join(["p = [''.join((",v,")) ",f,"]"]) exec e return p if (not perm) and repl: # ok v = ','.join(['c%s' % i for i in r0]) f = ' '.join(['for c%s in a' % i for i in r0]) i = ' and '.join(['(c%s>=c%s)' % (j,j-1) for j in r1]) e = ''.join(["p = [''.join((",v,")) ",f," if ",i,"]"]) exec e return p if perm and (not repl): # ok v = ','.join(['c%s' % i for i in r0]) f = ' '.join(['for c%s in a' % i for i in r0]) i = ' and '.join([' and '.join(['(c%s!=c%s)' % (j,k) for k in range(j)]) for j in r1]) e = ''.join(["p = [''.join((",v,")) ",f," if ",i,"]"]) exec e return p if (not perm) and (not repl): # ok v = ','.join(['c%s' % i for i in r0]) f = ' '.join(['for c%s in a' % i for i in r0]) i = ' and '.join(['(c%s>c%s)' % (j,j-1) for j in r1]) e = ''.join(["p = [''.join((",v,")) ",f," if ",i,"]"]) exec e return p
print '0123456789 taken 2 at a time'
p = ooloop6('0123456789',2,True,True) print print 'Permutations with Replacement: %6d' % (len(p)) print p
p = ooloop6('0123456789',2,True,False) print print 'Permutations without Replacement: %6d' % (len(p)) print p
p = ooloop6('0123456789',2,False,True) print print 'Combinations with Replacement: %6d' % (len(p)) print p
p = ooloop6('0123456789',2,False,False) print print 'Combinations without Replacement: %6d' % (len(p)) print p
print
print '0123456789 taken 3 at a time'
p = ooloop6('0123456789',3,True,True) print print 'Permutations with Replacement: %6d' % (len(p)) print p
p = ooloop6('0123456789',3,True,False) print print 'Permutations without Replacement: %6d' % (len(p)) print p
p = ooloop6('0123456789',3,False,True) print print 'Combinations with Replacement: %6d' % (len(p)) print p
p = ooloop6('0123456789',3,False,False) print print 'Combinations without Replacement: %6d' % (len(p)) print p
|
