¿Cómo puedo calcular un producto cartesiano de forma iterativa?

Esta pregunta pregunta cómo calcular el producto cartesiano de un número dado de vectores. Como la cantidad de vectores se conoce de antemano y es bastante pequeña, la solución se obtiene fácilmente con bucles nesteds.

Ahora suponga que se le proporciona, en el idioma de su elección, un vector de vectores (o una lista de listas, o conjuntos de conjuntos, etc.):

l = [ [1,2,3], [4,5], [6,7], [8,9,10], [11,12], [13] ] 

Si me pidieran que calculara su producto cartesiano, eso es

 [ [1,4,6,8,11,13], [1,4,6,8,12,13], [1,4,6,9,11,13], [1,4,6,9,12,13], ... ] 

Procederé con la recursión. Por ejemplo, en Python rápido y sucio,

 def cartesianProduct(aListOfLists): if not aListOfLists: yield [] else: for item in aListOfLists[0]: for product in cartesianProduct(aListOfLists[1:]): yield [item] + product 

¿Hay alguna manera fácil de calcularlo iterativamente ?

(Nota: la respuesta no necesita estar en python, y de todos modos soy consciente de que en python itertools hace el trabajo mejor, como en esta pregunta ).

1) Cree una lista de índices en las listas respectivas, inicializada a 0, es decir:

 indexes = [0,0,0,0,0,0] 

2) Ceda el elemento apropiado de cada lista (en este caso, el primero).

3) Incrementar el último índice por uno.

4) Si el último índice es igual a la longitud de la última lista, reinícielo a cero y lleve uno. Repite esto hasta que no haya acarreo.

5) Regrese al paso 2 hasta que los índices vuelvan a [0,0,0,0,0,0]

Es similar a cómo funciona el conteo, excepto que la base para cada dígito puede ser diferente.


Aquí hay una implementación del algoritmo anterior en Python:

 def cartesian_product(aListOfList): indexes = [0] * len(aListOfList) while True: yield [l[i] for l,i in zip(aListOfList, indexes)] j = len(indexes) - 1 while True: indexes[j] += 1 if indexes[j] < len(aListOfList[j]): break indexes[j] = 0 j -= 1 if j < 0: return 

Aquí hay otra forma de implementarlo usando trucos de módulo:

 def cartesian_product(aListOfList): i = 0 while True: result = [] j = i for l in aListOfList: result.append(l[j % len(l)]) j /= len(l) if j > 0: return yield result i += 1 

Tenga en cuenta que esto genera los resultados en un orden ligeramente diferente al de su ejemplo. Esto puede solucionarse iterando sobre las listas en orden inverso.

Itera de 0 a \Pi a_i_length para todo i .

 for ( int i = 0; i < product; i++ ) { // N is the number of lists int now = i; for ( int j = 0; j < N; j++ ) { // This is actually the index, you can get the value easily. current_list[j] = now % master_list[j].length; // shifts digit (integer division) now /= master_list[j].length; } } 

También hay algunas formas triviales de escribir esto para que no tenga que hacer el mismo trabajo dos veces.

Como usted solicitó una solución independiente del idioma, aquí hay una en bash, pero ¿podemos llamarla iterativa, recursiva, qué es? Es solo notación:

 echo {1,2,3},{4,5},{6,7},{8,9,10},{11,12},13 

tal vez lo suficientemente interesante.

 1,4,6,8,11,13 1,4,6,8,12,13 1,4,6,9,11,13 1,4,6,9,12,13 1,4,6,10,11,13 ... 

Solo tienes que administrar tu stack manualmente. Básicamente, haz lo que la recursividad hace por tu cuenta. Como la recursividad pone datos sobre cada llamada recursiva en una stack, simplemente haz lo mismo:

 Let L[i] = elements in vector i k = 0; st[] = a pseudo-stack initialized with 0 N = number of vectors while ( k > -1 ) { if ( k == N ) // solution, print st and --k if ( st[k] < L[k].count ) { ++st[k] ++k } else { st[k] = 0; --k; } } 

No probado, pero la idea funcionará. Espero no haberme perdido nada.

Edición : bueno, demasiado tarde, supongo. Esto es básicamente lo mismo que contar, simplemente otra forma de verlo.