Permutations of a list of lists

Question

I have a list like this:

l = [['a', 'b', 'c'], ['a', 'b'], ['g', 'h', 'r', 'w']]

I want to pick an element from each list and combine them to be a string.

For example: 'aag', 'aah', 'aar', 'aaw', 'abg', 'abh' ....

However, the length of the list l and the length of each inner list are all unknown before the program is running. So how can I do want I want?

Answer 1

Take a previous solution and use itertools.product(*l) instead.

Answer 2

If anybody's interested in the algorithm, here's a very simple way to use recursion to find the combos:

 l = [['a', 'b', 'c'], ['a', 'b'], ['g', 'h', 'r', 'w']]
 def permu(lists, prefix=''):
      if not lists:
           print prefix
           return
      first = lists[0]
      rest = lists[1:]
      for letter in first:
           permu(rest, prefix + letter)
 permu(l)

Answer 3

using recursion

def permutenew(l):
if len(l)==1:
    return l[0]
else:   
    lnew=[]
    for a in l[0]:
        for b in permutenew(l[1:]):
            lnew.append(a+b)
    return lnew

l = [['a', 'b', 'c'], ['a', 'b'], ['g', 'h', 'r', 'w']]
print permutenew(l)

Answer 4

Piggy-backing off of JasonWoof's answer. The following will create a list instead of printing. Be mindful that this may be very slow as it requires a lot of memory to store the values.

from __future__ import print_function
import itertools # Not actually used in the code below

def permu(lists):
    def fn(lists, group=[], result=[]):
        if not lists:
            result.append(group)
            return
        first, rest = lists[0], lists[1:]
        for letter in first:
            fn(rest, group + [letter], result)
    result = []
    fn(lists, result=result)
    return result

if __name__ == '__main__':
    ll = [ [[1, 2, 3], [5, 10], [42]],
           [['a', 'b', 'c'], ['a', 'b'], ['g', 'h', 'r', 'w']] ]
    nth = lambda i: 'Permutation #{0}:\n{1}'.format(i, '-'*16)

    # Note: permu(list) can be replaced with itertools.product(*l)
    [[print(p) for p in [nth(i)]+permu(l)+['\n']] for i,l in enumerate(ll)]

Result

Permutation #0:
----------------
[1, 5, 42]
[1, 10, 42]
[2, 5, 42]
[2, 10, 42]
[3, 5, 42]
[3, 10, 42]


Permutation #1:
----------------
['a', 'a', 'g']
['a', 'a', 'h']
['a', 'a', 'r']
['a', 'a', 'w']
['a', 'b', 'g']
['a', 'b', 'h']
['a', 'b', 'r']
['a', 'b', 'w']
['b', 'a', 'g']
['b', 'a', 'h']
['b', 'a', 'r']
['b', 'a', 'w']
['b', 'b', 'g']
['b', 'b', 'h']
['b', 'b', 'r']
['b', 'b', 'w']
['c', 'a', 'g']
['c', 'a', 'h']
['c', 'a', 'r']
['c', 'a', 'w']
['c', 'b', 'g']
['c', 'b', 'h']
['c', 'b', 'r']
['c', 'b', 'w']

---

Below is an equivalent substitution for itertools.product(*iterables[, repeat]):

This function is equivalent to the following code, except that the actual implementation does not build up intermediate results in memory:

def product(*args, **kwds):
    pools = list(map(tuple, args)) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)