Permutaciones de una lista de listas

Question

que tienen una lista como esta:

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

Quiero escoger un elemento de cada lista y combinarlos para ser una cadena.

Por ejemplo: 'AAG', 'aah', 'aar', 'aaw', 'ABG', 'abh' ....

Sin embargo, la longitud de la lista l y la longitud de cada lista interna es desconocida antes de que el programa se ejecute. Entonces, ¿cómo puedo querer lo que quiero?

Answer 1

Tome previous solution y use itertools.product(*l) en su lugar.

Answer 2

muy fácil con itertools.product:

>>> import itertools 
>>> list(itertools.product("abc", "ab", "ghrw")) 
[('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')] 

Answer 3

Si alguien está interesado en el algoritmo, aquí es una manera muy simple de usar recursividad para encontrar los 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 4

Aquí tiene

reduce(lambda a,b: [i+j for i in a for j in b], l) 

OUT: ['aag', 'aah', 'aar', 'aaw', 'abg', 'abh', 'abr', 'abw', 'bag', 'bah', 'bar', 'baw', 'bbg', 'bbh', 'bbr', 'bbw', 'cag', 'cah', 'car', 'caw', 'cbg', 'cbh', 'cbr', 'cbw'] 

Si quiere reutilizar/regeneralizar:

def opOnCombos(a,b, op=operator.add): 
    return [op(i,j) for i in a for j in b] 

def f(x): 
    return lambda a,b: opOnCombo(a,b,x) 

reduce(opOnCombos, l) //same as before 
reduce(f(operator.mul), l)) //multiply combos of several integer list 

Answer 5

usando recursión

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 6

Piggy-retrocediendo de JasonWoof's answer. Lo siguiente creará una lista en lugar de imprimir. Tenga en cuenta que esto puede ser muy lento, ya que requiere una gran cantidad de memoria para almacenar los valores.

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

Resultado

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

---

A continuación se muestra una sustitución equivalente para itertools.product(*iterables[, repeat]):

Esta función es equivalente al código siguiente, salvo que la ejecución real no se acumula resultados intermedios en la memoria:

def product(*args, **kwds): 
    pools = 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)