Getting all possible combinations of list items
Greg Krohn
all the possible combinations of the items in another list?
e.g.
another_list = ['a', 'b', 'c']
magic_algorithm(another_list) -> ['aa', 'ab', 'ac', 'ba', 'bc', 'bc', 'ca',
'cb', 'cc']
I know I could do this easily with nested 'fors', but that requires me to
know the length of the set. Is this a case for recursive functions? I hope
not, those things scare me. BTW, each item in another_list will be unique,
if that matters.
thanks for any ideas, suggestion, or urls
greg
--
Volucris (a) hotmail.com
"Eu não falo uma única palavra do português."
Ignacio Vazquez-Abrams
> Does anyone know of how I should go about generating a list whose keys are
> all the possible combinations of the items in another list?
> e.g.
>
> another_list = ['a', 'b', 'c']
>
> magic_algorithm(another_list) -> ['aa', 'ab', 'ac', 'ba', 'bc', 'bc', 'ca',
> 'cb', 'cc']
>
> I know I could do this easily with nested 'fors', but that requires me to
> know the length of the set. Is this a case for recursive functions? I hope
> not, those things scare me. BTW, each item in another_list will be unique,
> if that matters.
This solution treats the items in listin as values in a number system with the
radix equal to the number of items in the list and the number of positions in
count:
---
def magic_algorithm(listin, count):
for i in listin:
if type(i)!=type(''):
raise TypeError, 'all items in list passed to magic_algorithm must be strings'
l=len(listin)
return map(''.join, map(lambda x, count=count, l=l, listin=listin: map(lambda y, x=x, count=count, l=l, listin=listin: listin[((x/(l**y)) % l)], range(count)), xrange(l**count)))
---
---
>>> magic_algorithm(['a', 'b', 'c'], 2)
['aa', 'ba', 'ca', 'ab', 'bb', 'cb', 'ac', 'bc', 'cc']
>>>
---
--
Ignacio Vazquez-Abrams <ign...@openservices.net>
Greg Krohn
Thanks.
scratching my head over 'magic' code,
greg
--
Volucris (a) hotmail.com
"Eu não falo uma única palavra do português."
"Ignacio Vazquez-Abrams" <ign...@openservices.net> wrote in message
news:mailman.1000706420...@python.org...
Tim Peters
> ...
> scratching my head over 'magic' code,
Generators in 2.2 are "the natural" way to do this kind of thing. Here from
test_generators.py:
>>> def gcomb(x, k):
... "Generate all combinations of k elements from list x."
...
... if k > len(x):
... return
... if k == 0:
... yield []
... else:
... first, rest = x[0], x[1:]
... # A combination does or doesn't contain first.
... # If it does, the remainder is a k-1 comb of rest.
... for c in gcomb(rest, k-1):
... c.insert(0, first)
... yield c
... # If it doesn't contain first, it's a k comb of rest.
... for c in gcomb(rest, k):
... yield c
>>> seq = range(1, 5)
>>> for k in range(len(seq) + 2):
... print "%d-combs of %s:" % (k, seq)
... for c in gcomb(seq, k):
... print " ", c
0-combs of [1, 2, 3, 4]:
[]
1-combs of [1, 2, 3, 4]:
[1]
[2]
[3]
[4]
2-combs of [1, 2, 3, 4]:
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
3-combs of [1, 2, 3, 4]:
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
4-combs of [1, 2, 3, 4]:
[1, 2, 3, 4]
5-combs of [1, 2, 3, 4]:
That was posted to c.l.py before. Go to a search engine and look for it,
and you'll find an equivalent recursive (non-generator) routine too, which
looks *almost* exactly the same.
no-need-for-magic-just-need-care-at-the-boundaries-ly y'rs - tim
Martin von Loewis
> scratching my head over 'magic' code,
I prefer explicit loops over map and lambdas:
def magic_algorithm(another_list, count):
length = len(another_list)
result = []
for i in xrange(length**count):
number = ''
for pos in range(count):
# prepend the next digit
number = another_list[i % length] + number
i = i / length
result.append(number)
return result
Regards,
Martin
Alex Martelli
news:j4g09md...@informatik.hu-berlin.de...
> "Greg Krohn" <volu...@hotmail.com> writes:
>
> > scratching my head over 'magic' code,
>
> I prefer explicit loops over map and lambdas:
So do I, but building up a large string (here, the one
in the variable called number) by +'ing small ones in
a loop is a disaster. So, I'd make a small mod here:
> def magic_algorithm(another_list, count):
> length = len(another_list)
> result = []
> for i in xrange(length**count):
> number = ''
change this line to:
number = []
> for pos in range(count):
> # prepend the next digit
> number = another_list[i % length] + number
change this line to:
number.append(another_list[i % length])
> i = i / length
> result.append(number)
change this line to:
number.reverse()
result.append(''.join(number))
> return result
The number.reverse() line may not be needed if the
SET of strings returned, rather than their order,
is what one is after, as is typically the case.
I think it would be even clearer if we avoided the
inner loop in favour of a clearer one, i.e.,
rewriting the whole thing for clarity:
def magic_algorithm(another_list, count):
length = len(another_list)
result = []
for i in xrange(length**count):
number = []
for dig in digits_in_base(i, length, count):
number.append(another_list[dig])
result.append(''.join(number))
return result
where, e.g. and still emphasizing clarity:
def digits_in_base(value, base, ndigits):
result = ndigits*[0]
i = ndigits-1
while value and i>=0:
result[i] = value%base
value /= base
i -= 1
return result
With this auxiliary function at hand we may also
rewrite magic_algorithm using list comprehension,
e.g. for the inner loop only:
def magic_algorithm(another_list, count):
length = len(another_list)
result = []
for i in xrange(length**count):
result.append(''.join([another_list[dig]
for dig in digits_in_base(i, length, count)]))
return result
or for both loops:
def magic_algorithm(another_list, count):
length = len(another_list)
return [''.join([another_list[dig]
for dig in digits_in_base(i, length, count)])
for i in xrange(length**count)]
but either or both of these might be considered as
over-application of the list comprehension form,
depending of course on one's attitude to list
comprehension form itself. Personally, I prefer
the penultimate one, because it seems to me that
the last one is hard to follow -- it's unusual to
have a list comprehension inside another list
comprehension, after all. But there's not much to
choose among them except personal taste issues:-).
Alex
Paul Winkler
>Does anyone know of how I should go about generating a list whose keys are
>all the possible combinations of the items in another list?
>e.g.
>
>another_list = ['a', 'b', 'c']
>
>magic_algorithm(another_list) -> ['aa', 'ab', 'ac', 'ba', 'bc', 'bc', 'ca',
>'cb', 'cc']
Here's a simple one:
def magic_algorithm(alist):
result = []
for s in alist:
result.extend([s + s2 for s2 in alist])
return result
Or if you wanted to exclude duplicates (e.g. "aa", "bb", etc.):
def m(alist):
"""This version will not produce combinations like aa, bb, cc..."""
result = []
count = len(alist)
for i in range(count):
elsewhere = range(0, i) + range(i + 1, count)
result.extend([alist[i] + alist[j] for j in elsewhere])
return result
--PW
Quinn Dunkan
>all the possible combinations of the items in another list?
>I know I could do this easily with nested 'fors', but that requires me to
>know the length of the set. Is this a case for recursive functions? I hope
>not, those things scare me. BTW, each item in another_list will be unique,
>if that matters.
You've already gotten a lot of non-recursive solutions, which is good since
this is python, not scheme. But if you can get over your fear of recursion,
you may find it a very congenial way to think of such problems. A recursive
solution would begin with the observation that the permutations of a list
consist of each of the elements of the list followed by all the permutations
of the rest of the elements.
Translating that into python will not be idiomatic or pretty or efficient, but
it will be simple and thus more likely correct, and may help you think of an
iterative solution.