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

Question

This question 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 anidados.

Ahora supongamos que se le da, en el idioma de su elección, un vector de vectores (o lista de listas, o conjunto de juegos, etc.):

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

Si se me pidió que calcular su Producto cartesiano, es decir

[ [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 recursividad. Por ejemplo, en rápida & pitón sucia,

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

¿Hay una manera fácil de calcular que iterativa?

(Nota: La respuesta no tiene por qué ser en Python, y de todos modos yo soy consciente de que en itertools pitón hace el trabajo mejor, al igual que en this question.)

Answer 1

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

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

2) Rendimiento el elemento apropiado de cada lista (en este caso la primera).

3) Aumente el último índice en 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) Volver al paso 2 hasta que los índices de envolver de nuevo a [0,0,0,0,0,0]

Es similar a cómo contar las obras, excepto la base para cada dígito puede ser diferente .

---

Aquí es 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í es otra manera de ponerla en práctica el uso de 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 este emite el resultados en un orden ligeramente diferente que en su ejemplo. Esto puede solucionarse iterando sobre las listas en orden inverso.

Answer 2

Iterar de 0 a \Pi a_i_length para todos 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.

Answer 3

Solo tiene que administrar su pila manualmente. Básicamente, haz lo que la recursividad hace por tu cuenta.Desde la recursividad pone los datos sobre cada llamada recursiva en una pila, que acaba de hacer el 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 han sido evaluados, pero la idea va a funcionar. Espero no haberme perdido nada.

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

Answer 4

Como usted pidió 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 ...