Producto cruzado de conjuntos mediante recursión.

Escribí la siguiente rutina recursiva para calcular el producto cruzado de dos conjuntos.

def combine(input1,input2,output): if len(input2)==0: return output else: for num in input1: output.append((num,input2[0])) combine(input1,input2[1:],output) input1=[1 2 5] input2=[2 3] output=[(1,2), (1,3), (2,2),(2,3),(5,2),(5,3)] 

¿Es posible mejorar la recursión, por ejemplo, eliminar el bucle en else y tratar de hacer la misma función? Estoy buscando diferentes maneras de resolver el problema.

Edición: No busco una solución con algo incorporado. Buscando cómo puedo hacer la recursión de manera diferente, y no usar itertools.product.

La definición recursiva más simple del producto cartesiano que se me ocurre se ve así. Puede ver que al igual que el suyo, esto tiene un bucle; en realidad, dos bucles integrados en una lista de comprensión. A diferencia del tuyo, esto puede manejar dos o más secuencias:

 def product(*seqs): if not seqs: return [[]] else: return [[x] + p for x in seqs[0] for p in product(*seqs[1:])] 

Aquí hay un recorrido para darle una idea de cómo funciona. Por definición, el producto cartesiano de una secuencia vacía ( product() ) es una secuencia que contiene la secuencia vacía. En otras palabras, product() == [[]] – vea aquí por qué.

Ahora digamos que llamamos product([1, 2, 3])seqs no está vacío, por lo que el valor de retorno es el resultado de la lista de comprensión. En este caso, el product(*seqs[1:]) == product(*[]) == product() == [[]] , por lo que la lista de comprensión es equivalente a esto:

 [[x] + p for x in seqs[0] for p in [[]] ] 

Que es equivalente a todos estos:

 [[x] + [] for x in seqs[0]] [[x] for x in seqs[0]] [[1], [2], [3]] 

Añadiendo otra secuencia, tenemos product([4, 5, 6], [1, 2, 3]) . Ahora la lista de comprensión se ve así:

 [[x] + p for x in [4, 5, 6] for p in product(*seqs[1:])] [[x] + p for x in [4, 5, 6] for p in [[1], [2], [3]]] [[4, 1], [4, 2], [4, 3], [5, 1], [5, 2], [5, 3], [6, 1], [6, 2], [6, 3]] 

El patrón continúa desde allí; para cada secuencia adicional, cada uno de los valores en la secuencia se antepone a cada uno de los valores en el producto cartesiano de las siguientes secuencias.

Usar itertools

 import itertools print list(itertools.product(input1, input2)) 

Semánticamente esto es equivalente a:

 for i_1 in input_1: for i_2 in input_2: for i_3 in input_3: ... for i_n in input_n: #do something with i_1, i_2, i_3, ..., i_n 

Donde n es el número de argumentos que pasas al product .