Ich habe ein Setup, das so aussieht:
%Vor%Ich kenne die Größe der Arrays nicht, während ich den Code schreibe. Ich versuche, das gesamte Setup zu durchlaufen, um alle möglichen Kombinationen zu generieren:
141
144
146
151
154
156
341
...
Ich verwende derzeit Rekursion, um dies zu erreichen:
%Vor%Ich habe 2 Fragen dazu:
Ich erinnere mich, dass die Rekursion in Vorlesungen immer durch Schleifen ersetzt werden kann, aber ich kann das in diesem Fall nicht tun. Wie würde eine Loop-Version von diesem aussehen?
Gibt es einen besseren Weg, dieses Problem zu lösen?
Hier ist eine nicht-rekursive Methode, um alle Kombinationen von Array-Elementen auszugeben. Es ist definitiv komplexer als die rekursive Lösung. Es funktioniert, indem ein Datensatz in einem zusätzlichen Array gespeichert wird, dessen Nummer kürzlich in jedem Array in der Liste ausgegeben wurde.
%Vor%Ausgaben:
%Vor%Nun, es kann ohne Rekursion gemacht werden, wenn Sie ein Array, eine Liste oder irgendetwas anderes pflegen, das Ihnen sagt, wo Sie sich in jedem der Arrays befinden.
Nehmen wir an, wir führen eine Liste von Elementen wie folgt:
%Vor% Die Idee ist, dass wir jedes Array durchlaufen, sagen wir das {4, 5} -Array. Wir fangen mit den Vieren an, da wir unsere Schleife durchlaufen werden, wir werden das auf die Fünf aktualisieren. Aber dann ändert sich das Element oben und wir müssen wieder zu den Vier gehen. Diese Klasse hilft uns dabei.
Also bereiten wir unsere Indexliste vor:
%Vor%Das ist ziemlich einfach - wir gehen einfach durch unsere Liste und sammeln die Längen, um später zu wissen, wann wir jeden Index auf Null setzen müssen.
In jeder Iteration sollten wir die Liste durchgehen und die Zahlen im aktuellen Index jedes Arrays ausdrucken. Wenn wir also einen Index von 2 für das erste Array, 1 für das zweite und 0 für das letzte Array haben, sammeln wir 4 , 5 und 1 von Ihrem Beispiel.
Nun ist das wirkliche "Fleisch" dieser Lösung die Aktualisierung der Indizes. Es ist ungefähr so, als würde man einer Zahl 1 hinzufügen. Stellen Sie sich vor, Sie haben die Nummer 1958 und fügen 1 hinzu. Es wird 1959 . Jetzt fügen Sie 1 erneut hinzu. Also wird die 9 zu 0 , und Sie müssen die 1 zu der 5 tragen. Sie haben jetzt 1960 . Mach weiter so und du wirst 1999 erreichen. An diesem Punkt addierst du 1, nimmst die 9, trägst nach links, dann nulst du es auch und trägst nach links, dann nulltest du nach, und trägst nach links, und du bekommst 2000 .
Auf die gleiche Weise - von rechts beginnend und durch die linke gehend, wenn wir die 1 tragen müssen - aktualisieren wir auch unsere Indexliste:
%Vor%Wenn wir "carry" vom Index ganz links haben - dem Index, der zum Kopf unserer ursprünglichen Liste gehört - bedeutet das, dass wir das Programm beendet haben, da wir alle Elemente im ersten Array durchlaufen haben. Wenn dies geschieht, gibt die obige Methode true zurück.
Jetzt müssen wir nur noch unsere Methoden aufrufen:
%Vor% Dies ist die Lösung OHNE mit stacks / queues / linked list . Rein mit einfachen Schleifen gemacht. Die einzige Datenstruktur, die ich verwende, ist ein 1D-Array.
Die Idee ist, ein 1D-Array zu verwenden, um sich den Zustand zu merken. Status, der mit 1D-Array dargestellt wird, um zu bestimmen, welcher Array-Index gedruckt werden soll.
AUSGABE:
%Vor%Gibt es einen besseren Weg, um dieses Problem zu lösen?
Ein abstrakterer Ansatz:
Dies funktioniert, da Ihr Problem so modelliert werden kann, dass jede mögliche Ausführung durch ein verteiltes System aufgelistet wird, in dem die Gesamtzahl der Prozesse der Länge des längsten in der Liste gefundenen Arrays entspricht.