Ich schreibe ein Code-Segment, das jede Permutation von n Ziffern durchläuft. Wenn zum Beispiel n = 3 ist, würde ich jedes der folgenden Elemente durchlaufen wollen:
0, 0, 0
...
0, 1, 0
...
1, 0, 0
...
2, 3, 4
...
9, 9, 9
Dies ist sehr einfach mit geschachtelten for-Schleifen zu programmieren:
%Vor%Aber ich möchte das für n Ziffern verallgemeinern. Wenn zum Beispiel n = 10, brauche ich jetzt 10 verschachtelte für Schleifen.
Ich habe darüber nachgedacht und festgestellt, dass das Problem durch Rekursion gelöst werden kann (Tiefensuche zuerst durch einen Baum, wobei jeder Knoten 10 Kinder hat, 0 bis 10, und in der Tiefe stoppen n). Aber ich strebe eine hohe Leistung an, deshalb möchte ich aufgrund des Overheads keine Rekursion verwenden. Welche anderen Alternativen habe ich?
Wenn Sie verschachtelte Schleifen mit einem einzigen ohne Rekursion simulieren möchten, können Sie dies tun, indem Sie für jede Schleifenvariable eine Reihe von Zuständen (oder Slots) verwalten, was mit einem Array einfach durchgeführt werden kann. Das Schleifen wird dann zu einer einfachen Sache, "1" zu dieser Anordnung hinzuzufügen, wobei die Übertragsoperationen wie benötigt durchgeführt werden. Wenn Ihre Verschachtelungstiefe n ist und Ihre maximale Grenze für jede Schleife b ist, dann ist die Laufzeit dafür 0 (b ^ n), da nur die Übertragsoperationen ausgeführt werden kostet dich höchstens O (b ^ n) (Ich werde die Algebra hier überspringen).
Hier ist der funktionierende C ++ - Code ( aktualisiert , um Drews Kommentar zu integrieren):
%Vor%Wenn Sie die Permutation für alle Ziffern für eine bestimmte Länge wünschen, wie Sie Beispiel von 3 Ziffern gezeigt haben. Anstatt 3 verschachtelte Schleifen auszuführen, führe eine einzige Schleife von 10 ^ 3 aus, die dir alle Permutationen geben wird.
Teilen Sie die erhaltene Zahl in jeder Iteration in Ziffern, wenn Sie sie für die Indizierung verwenden möchten.
Sie brauchen also nur eine Schleife statt verschachtelte Schleifen.
Im generellen Fall, wenn Sie Rekursion zu Flat-Code ersetzen möchten, sollten Sie den Stack (LIFO) verwenden. Also, wenn Sie einen rekursiven Algorithmus haben:
%Vor%Sie können es in LIFO-basierte konvertieren, indem Sie lokale Variablen speichern (in diesem Fall str und i):
%Vor%Tags und Links c++ performance recursion tree for-loop