Wie kann ich ein kartesisches Produkt iterativ berechnen?

Question

This question fragt, wie man das kartesische Produkt einer gegebenen Anzahl von Vektoren berechnet. Da die Anzahl der Vektoren im voraus bekannt und eher klein ist, wird die Lösung leicht mit verschachtelten for-Schleifen erhalten.

Nehmen wir nun an, dass Sie gegeben sind, um einen Vektor von Vektoren in der Sprache Ihrer Wahl (oder eine Liste von Listen oder von Sätzen gesetzt usw.):

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

Wenn ich gebeten wurde, seine zu berechnen Kartesisches Produkt, das ist

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

Ich würde mit Rekursion fortfahren. Zum Beispiel in schnellen & schmutzig Python,

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

Gibt es eine einfache Möglichkeit, es zu berechnen iterativ?

(Anmerkung: Die Antwort muss nicht in Python sein, und trotzdem bewusst, dass ich bin, dass in Python itertools macht den Job besser, als in this question.)

Answer 1

1) Erstellen Sie eine Liste von Indizes in die entsprechenden Listen, initialisiert auf 0, das heißt:

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

2) Ausbeute das entsprechende Element aus jeder Liste (in diesem Fall die erste).

3) Erhöhen Sie den letzten Index um eins.

4) Wenn der letzte Index der Länge der letzten Liste entspricht, setzen Sie ihn auf Null zurück und tragen Sie einen. Wiederholen Sie dies, bis kein Transport mehr möglich ist.

5) Gehen Sie zurück zu Schritt 2, bis die Indizes [0,0,0,0,0,0]

wickeln zurück

Es ist ähnlich, wie funktioniert das Zählen, mit Ausnahme der Basis für jede Ziffer unterschiedlich sein können .

---

Hier ist eine Implementierung des obigen Algorithmus in 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 

---

Hier ist ein weiterer Weg, um es mit Modulo-Tricks zu implementieren:

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 

Beachten Sie, dass dies die Ausgänge ergibt eine etwas andere Reihenfolge als in Ihrem Beispiel. Dies kann behoben werden, indem die Listen in umgekehrter Reihenfolge durchlaufen werden.

Answer 2

Iterieren Sie von 0 bis \Pi a_i_length für alle 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; 
    } 
} 

Es gibt auch einige triviale Möglichkeiten, dies zu schreiben, so dass Sie nicht zweimal die gleiche Arbeit machen müssen.

Answer 3

Sie müssen nur Ihren Stapel manuell verwalten. Im Grunde tun, was Rekursion auf eigene Faust macht.Da Rekursion auf einem Stapel Daten zu jedem rekursiven Aufruf setzt, tun Sie nur das gleiche:

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; 
    } 
} 

Nicht getestet, aber die Idee arbeiten. Hoffentlich habe ich nichts vermisst.

Bearbeiten: Nun, zu spät, denke ich. Das ist im Grunde dasselbe wie das Zählen, nur eine andere Art, es zu betrachten.

Answer 4

Da Sie nach einer sprachunabhängigen Lösung gefragt haben, ist hier eine in bash, aber können wir es iterativ, rekursiv nennen, was ist das? Es ist nur Notation:

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

vielleicht interessant genug.

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 ...