¿Obtener el producto cartesiano de una serie de listas?

¿Cómo puedo obtener el producto cartesiano (todas las combinaciones posibles de valores) de un grupo de listas?

Entrada:

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]

Salida deseada:

[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), (2, 'a', 5) ...]

itertools.product

Disponible desde Python 2.6.

import itertools

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]
for element in itertools.product(*somelists):
    print(element)

Que es lo mismo que

for element in itertools.product([1, 2, 3], ['a', 'b'], [4, 5]):
    print(element)

import itertools
>>> for i in itertools.product([1,2,3],['a','b'],[4,5]):
...         print i
...
(1, 'a', 4)
(1, 'a', 5)
(1, 'b', 4)
(1, 'b', 5)
(2, 'a', 4)
(2, 'a', 5)
(2, 'b', 4)
(2, 'b', 5)
(3, 'a', 4)
(3, 'a', 5)
(3, 'b', 4)
(3, 'b', 5)
>>>

Para Python 2.5 y anteriores:

>>> [(a, b, c) for a in [1,2,3] for b in ['a','b'] for c in [4,5]]
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), 
 (2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5), 
 (3, 'b', 4), (3, 'b', 5)]

Aquí hay una versión recursiva de product()(solo una ilustración):

def product(*args):
    if not args:
        return iter(((),)) # yield tuple()
    return (items + (item,) 
            for items in product(*args[:-1]) for item in args[-1])

Ejemplo:

>>> list(product([1,2,3], ['a','b'], [4,5])) 
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), 
 (2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5), 
 (3, 'b', 4), (3, 'b', 5)]
>>> list(product([1,2,3]))
[(1,), (2,), (3,)]
>>> list(product([]))
[]
>>> list(product())
[()]

con itertools.product :

import itertools
result = list(itertools.product(*somelists))

Usaría la comprensión de la lista:

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]

cart_prod = [(a,b,c) for a in somelists[0] for b in somelists[1] for c in somelists[2]]

Aquí hay un generador recursivo, que no almacena ninguna lista temporal

def product(ar_list):
    if not ar_list:
        yield ()
    else:
        for a in ar_list[0]:
            for prod in product(ar_list[1:]):
                yield (a,)+prod

print list(product([[1,2],[3,4],[5,6]]))

Salida:

[(1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6)]

En Python 2.6 y superior puedes usar 'itertools.product`. En versiones anteriores de Python, puede usar el siguiente código equivalente (casi ver documentación) de la documentación , al menos como punto de partida:

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    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)

El resultado de ambos es un iterador, por lo que si realmente necesita una lista para el procesamiento adicional, úselo list(result).

Aunque ya hay muchas respuestas, me gustaría compartir algunos de mis pensamientos:

Enfoque iterativo

def cartesian_iterative(pools):
  result = [[]]
  for pool in pools:
    result = [x+[y] for x in result for y in pool]
  return result

Enfoque recursivo

def cartesian_recursive(pools):
  if len(pools) > 2:
    pools[0] = product(pools[0], pools[1])
    del pools[1]
    return cartesian_recursive(pools)
  else:
    pools[0] = product(pools[0], pools[1])
    del pools[1]
    return pools
def product(x, y):
  return [xx + [yy] if isinstance(xx, list) else [xx] + [yy] for xx in x for yy in y]

Enfoque Lambda

def cartesian_reduct(pools):
  return reduce(lambda x,y: product(x,y) , pools)

Enfoque recursivo:

def rec_cart(start, array, partial, results):
  if len(partial) == len(array):
    results.append(partial)
    return 

  for element in array[start]:
    rec_cart(start+1, array, partial+[element], results)

rec_res = []
some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]  
rec_cart(0, some_lists, [], rec_res)
print(rec_res)

Enfoque iterativo:

def itr_cart(array):
  results = [[]]
  for i in range(len(array)):
    temp = []
    for res in results:
      for element in array[i]:
        temp.append(res+[element])
    results = temp

  return results

some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]  
itr_res = itr_cart(some_lists)
print(itr_res)

Una modificación menor a la solución del generador recursivo anterior en sabor variadic:

def product_args(*args):
    if args:
        for a in args[0]:
            for prod in product_args(*args[1:]) if args[1:] else ((),):
                yield (a,) + prod

Y, por supuesto, un contenedor que hace que funcione exactamente igual que esa solución:

def product2(ar_list):
    """
    >>> list(product(()))
    [()]
    >>> list(product2(()))
    []
    """
    return product_args(*ar_list)

con una compensación : verifica si la recursión debe romperse en cada bucle externo, y una ganancia : no hay rendimiento en una llamada vacía, por ejemplo product(()), lo que supongo que sería semánticamente más correcto (ver el doctest).

Con respecto a la comprensión de la lista: la definición matemática se aplica a un número arbitrario de argumentos, mientras que la comprensión de la lista solo puede tratar con un número conocido de ellos.

Solo para agregar un poco a lo que ya se ha dicho: si usa sympy, puede usar símbolos en lugar de cadenas, lo que los hace matemáticamente útiles.

import itertools
import sympy

x, y = sympy.symbols('x y')

somelist = [[x,y], [1,2,3], [4,5]]
somelist2 = [[1,2], [1,2,3], [4,5]]

for element in itertools.product(*somelist):
  print element

Sobre sympy .

Creo que esto funciona:

def cartesian_product(L):  
   if L:
       return {(a,) + b for a in L[0] 
                        for b in cartesian_product(L[1:])}
   else:
       return {()}

Enfoque de Stonehenge:

def giveAllLists(a, t):
    if (t + 1 == len(a)):
        x = []
        for i in a[t]:
            p = [i]
            x.append(p)
        return x
    x = []

    out = giveAllLists(a, t + 1)
    for i in a[t]:

        for j in range(len(out)):
            p = [i]
            for oz in out[j]:
                p.append(oz)
            x.append(p)
    return x

xx= [[1,2,3],[22,34,'se'],['k']]
print(giveAllLists(xx, 0))

salida:

[[1, 22, 'k'], [1, 34, 'k'], [1, 'se', 'k'], [2, 22, 'k'], [2, 34, 'k'], [2, 'se', 'k'], [3, 22, 'k'], [3, 34, 'k'], [3, 'se', 'k']]