Getting all possible combinations of list items

[Alex Martelli]

"Martin von Loewis" <loewis at informatik.hu-berlin.de> wrote in message
news:j4g09mdvvt.fsf at informatik.hu-berlin.de...
> "Greg Krohn" <volucris at 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