Verständnis der Rekursion zum generieren von Permutationen

Ich finde Rekursion, abgesehen von sehr geradlinig, wie die Faktoren -, die sehr schwer zu verstehen. Das folgende snippet gibt alle Permutationen eines Strings. Kann mir jemand helfen, es zu verstehen. Was ist der Weg, um darüber zu gehen zu verstehen, Rekursion richtig.

void permute(char a[], int i, int n)
{
   int j;
   if (i == n)
     cout << a << endl;
   else
   {
       for (j = i; j <= n; j++)
       {
          swap(a[i], a[j]);          
          permute(a, i+1, n);
          swap(a[i], a[j]);
       }
   }
} 

int main()
{
   char a[] = "ABCD";
   permute(a, 0, 3);
   getchar();
   return 0;
}

Skizzieren Sie es heraus auf Papier, oder Sie können auch versuchen Einzelschritt durch den code in einem debugger.
Hinzufügen für einige eine neue: Schreiben Sie ein C-Programm zum drucken aller Permutationen einer gegebenen Zeichenfolge
Erste Sache ist, dass die Rekursion nur manchmal Ergebnisse in den eleganten, intuitiven Lösungen. Manchmal ist die Lösung ist elegant aber überhaupt nicht intuitiv, wie ich glaube, es ist hier. Manchmal ist es weder elegant, noch intuitiv. Könnte es etwas unelegant und doch intuitiv? Ich weiß es nicht. In diesem Fall ist die erste Sache, die Sie brauchen, um zu verstehen, konzeptionell, ist, wie man alle Permutationen, die durch vertauschen von verschiedenen element-Paare im array. Dann müssen Sie verstehen, wie der rekursive Algorithmus wird angewendet, um die Durchführung dieses Konzepts. Es kann helfen, ziehen Sie aus der rekursions-Baum auf Papier bei jedem Schritt.
dies ist erschöpfend Rekursion und als Sazzad Hissain Khan sagte in seiner Antwort unter es ist der Kern der backtracking, cf Seite 2 see.stanford.edu/materials/icspacs106b/... backtracking verwendet wird, also eingeschränkte Vermehrung Probleme

InformationsquelleAutor Nemo | 2011-09-24

c++recursion

53

PaulR hat den richtigen Tipp. Sie haben zu laufen, durch den code von "hand" (mit den Werkzeugen, die Sie wollen - Debugger, Papier, Protokollierung der Funktionsaufrufe und Variablen an bestimmten Punkten), bis Sie es verstehen. Für eine Erklärung des Codes, Verweise ich Sie auf quasiverse ausgezeichnete Antwort.

Vielleicht ist diese Visualisierung des call-Graphen mit einer etwas kleineren saite macht es deutlicher, wie es funktioniert:

Die Grafik wurde mit graphviz.
```
//x.dot
//dot x.dot -Tpng -o x.png
digraph x {
rankdir=LR
size="16,10"

node [label="permute(\"ABC\", 0, 2)"] n0;
 node [label="permute(\"ABC\", 1, 2)"] n1;
  node [label="permute(\"ABC\", 2, 2)"] n2;
  node [label="permute(\"ACB\", 2, 2)"] n3;
 node [label="permute(\"BAC\", 1, 2)"] n4;
  node [label="permute(\"BAC\", 2, 2)"] n5;
  node [label="permute(\"BCA\", 2, 2)"] n6;
 node [label="permute(\"CBA\", 1, 2)"] n7;
  node [label="permute(\"CBA\", 2, 2)"] n8;
  node [label="permute(\"CAB\", 2, 2)"] n9;

n0 -> n1 [label="swap(0, 0)"];
n0 -> n4 [label="swap(0, 1)"];
n0 -> n7 [label="swap(0, 2)"];

n1 -> n2 [label="swap(1, 1)"];
n1 -> n3 [label="swap(1, 2)"];

n4 -> n5 [label="swap(1, 1)"];
n4 -> n6 [label="swap(1, 2)"];

n7 -> n8 [label="swap(1, 1)"];
n7 -> n9 [label="swap(1, 2)"];
}
```
Es kann hilfreich sein, um die Visualisierung der Aufruf-stack als ein Baum. Es ist auch erwähnenswert, dass wenn Sie einen rekursiven Aufruf, Sie vorab nach einem einzelnen Zweig des Baumes, und eine weitere Niederlassung Hinzugefügt wird mit jeder iteration der " for "oder" while " - Schleife. Eine verwirrende Sache über dieses problem ist der zweite swap nach dem rekursiven Aufruf permutiert. Dies kann interpretiert werden als 'unswap' und ist erforderlich, weil das char-array wird per Referenz übergeben, nicht als Wert, und jedes mal, wenn Sie vertauschen der array-Elemente wird die änderung sichtbar nach unten stream.

InformationsquelleAutor user786653

Er wählt die einzelnen Zeichen aus allen möglichen Zeichen Links:

void permute(char a[], int i, int n)
{
    int j;
    if (i == n)                  //If we've chosen all the characters then:
       cout << a << endl;        //we're done, so output it
    else
    {
        for (j = i; j <= n; j++) //Otherwise, we've chosen characters a[0] to a[j-1]
        {                        //so let's try all possible characters for a[j]
            swap(a[i], a[j]);    //Choose which one out of a[j] to a[n] you will choose
            permute(a, i+1, n);  //Choose the remaining letters
            swap(a[i], a[j]);    //Undo the previous swap so we can choose the next possibility for a[j]
        }
    }
}

ausgezeichnete Antwort
Ihre Kommentare in den code, war wirklich hilfreich für mich, danke 🙂

InformationsquelleAutor quasiverse

17

Rekursion zu verwenden, effektiv in der Gestaltung, die Sie lösen das problem, indem vorausgesetzt, Sie haben es bereits gelöst.
Die geistige Sprungbrett für das aktuelle problem ist "wenn ich könnte, berechnen Sie die Permutationen der n-1 Zeichen, dann könnte ich mir die Berechnung der Permutationen von n Zeichen, indem Sie jede ein in drehen und anfügen der Permutationen der restlichen n-1 Zeichen, die ich bin vorgibt, ich weiß schon, was zu tun ist".

Dann müssen Sie einen Weg, das zu tun, was heißt "durchschlagen" der Rekursion. Da jede neue sub-problem ist kleiner als der Letzte, vielleicht wirst du irgendwann einen sub-sub-problem, dass Sie WIRKLICH wissen, wie zu lösen.

In diesem Fall, Sie wissen schon alle die Permutationen von EINEM Charakter - es ist nur der Charakter. Damit Sie wissen, wie lösen es für n=1 und für jede Zahl, die man mehr als eine Zahl, die Sie lösen kann, und du bist fertig. Dieses ist sehr eng verwandt zu so genannten mathematischen Induktion.

InformationsquelleAutor phunctor

Verständnis der Rekursion zum generieren von Permutationen

Diesem code und Referenz könnte Ihnen helfen, es zu verstehen.

//C program to print all permutations with duplicates allowed
#include <stdio.h>
#include <string.h>

/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}

/* Driver program to test above functions */
int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permute(str, 0, n-1);
    return 0;
}

Referenz: Geeksforgeeks.org

InformationsquelleAutor Sazzad Hissain Khan

Obwohl es wenig alte Frage und schon beantwortet dachte hinzufügen, meine Eingaben zu helfen, neue Besucher. Auch die Planung zu erklären, die Laufzeit, ohne sich auf eine Rekursive Versöhnung.

Ich geschrieben habe das Beispiel in C#, aber einfach zu verstehen für die meisten Programmierer.

static int noOfFunctionCalls = 0;
static int noOfCharDisplayCalls = 0;
static int noOfBaseCaseCalls = 0;
static int noOfRecursiveCaseCalls = 0; 
static int noOfSwapCalls = 0;
static int noOfForLoopCalls = 0;

static string Permute(char[] elementsList, int currentIndex)
{
    ++noOfFunctionCalls;

    if (currentIndex == elementsList.Length)
    {
        ++noOfBaseCaseCalls;        
        foreach (char element in elementsList)
        {
            ++noOfCharDisplayCalls;

            strBldr.Append(" " + element);
        }
        strBldr.AppendLine("");
    }
    else
    {
        ++noOfRecursiveCaseCalls;

        for (int lpIndex = currentIndex; lpIndex < elementsList.Length; lpIndex++)
        {
            ++noOfForLoopCalls;

            if (lpIndex != currentIndex)
            {
                ++noOfSwapCalls;
                Swap(ref elementsList[currentIndex], ref elementsList[lpIndex]);
            }

            Permute(elementsList, (currentIndex + 1));

            if (lpIndex != currentIndex)
            {
                Swap(ref elementsList[currentIndex], ref elementsList[lpIndex]);
            }
        }
    }
    return strBldr.ToString();
}

static void Swap(ref char Char1, ref char Char2)
{
    char tempElement = Char1;
    Char1 = Char2;
    Char2 = tempElement;
}      

public static void StringPermutationsTest()
{
    strBldr = new StringBuilder();
    Debug.Flush();

    noOfFunctionCalls = 0;
    noOfCharDisplayCalls = 0;
    noOfBaseCaseCalls = 0;
    noOfRecursiveCaseCalls = 0;
    noOfSwapCalls = 0;
    noOfForLoopCalls = 0;

    //string resultString = Permute("A".ToCharArray(), 0);
    //string resultString = Permute("AB".ToCharArray(), 0);
    string resultString = Permute("ABC".ToCharArray(), 0);
    //string resultString = Permute("ABCD".ToCharArray(), 0);
    //string resultString = Permute("ABCDE".ToCharArray(), 0);

    resultString += "\nNo of Function Calls : " + noOfFunctionCalls;
    resultString += "\nNo of Base Case Calls : " + noOfBaseCaseCalls;
    resultString += "\nNo of General Case Calls : " + noOfRecursiveCaseCalls;
    resultString += "\nNo of For Loop Calls : " + noOfForLoopCalls;
    resultString += "\nNo of Char Display Calls : " + noOfCharDisplayCalls;
    resultString += "\nNo of Swap Calls : " + noOfSwapCalls;

    Debug.WriteLine(resultString);
    MessageBox.Show(resultString);       
}

Schritte:
Für z.B., wenn wir an die Eingabe als "ABC".

Permutationen Methode aufgerufen vom Main zum ersten mal. Also Aufruf mit Index 0 und das ist der erste Anruf.
In der else-Teil in der for-Schleife wiederholen wir von 0 bis 2 machen 1 rufen jedes mal.
Unter each-Schleife Durchlaufen wir rekursiv aufrufen mit LpCnt + 1.
4.1 Wenn der index 1 ist, dann 2 rekursive Aufrufe.
4.2 Wenn index 2 ist, dann ist 1 rekursive Aufrufe.

Also von Punkt 2 zu 4.2 insgesamt Anrufe sind 5 für jede Schleife und insgesamt 15 Anrufe + main entry call = 16.
Jedes mal, wenn loopCnt 3, dann if-Bedingung ausgeführt wird.

Vom Diagramm können wir sehen, loop-Anzahl für immer 3 total 6 mal, d.h. Fakultaet mit dem Wert 3, d.h. die Eingabe "ABC" Länge.

If-Anweisung die for-Schleife wiederholt, wird 'n' mal auf anzeigen chars aus dem Beispiel "ABC", also 3.
Insgesamt 6-mal (Factorial mal), die wir eingehen, wenn an die Anzeige der Permutationen.
So ist die Gesamt-Laufzeit = n X n!.

Habe ich einige statische CallCnt Variablen und die Tabelle zu verstehen, jede Zeile die Ausführung im detail.

Experten, fühlen Sie sich frei zu Bearbeiten, meine Antwort oder Kommentar, wenn alle meine details nicht klar sind oder falsch, ich bin glücklich, Sie zu korrigieren.

Verständnis der Rekursion zum generieren von Permutationen

Downloaden Sie den Beispielcode und andere Proben aus hier

InformationsquelleAutor Sai

2

Denken Sie über die Rekursion einfach als eine Anzahl von Ebenen. Auf jeder Ebene sind, laufen Sie ein Stück des Codes haben, werden Sie hier läuft eine for-Schleife n-i mal auf jeder Ebene. in diesem Fenster wird eine Verringerung auf jeder Ebene. n-i-Zeiten, n-(i+1) - mal, n-(i+2) - mal,..2,1,0 Zeiten.

Hinblick auf string-Manipulationen und permutation, denke, dass der string einfach als ein 'set' von chars. "abcd" als {'a', 'b', 'c', 'd'}. Permutation ändert diese 4 Elemente auf alle möglichen Arten. Oder wie wählen 4 Elemente aus der diese 4 Elemente in unterschiedlicher Weise. In den Permutationen die Reihenfolge nicht egal. abcd unterscheidet sich von acbd. wir generieren müssen, beide.

Den rekursiven code, indem Sie genau das tut. In meinem string vor "abcd", Ihre rekursiven code kann ausgeführt werden 4 Iterationen (Ebenen). In der ersten iteration haben Sie 4 Elemente, um von zu wählen. zweiten iteration, haben Sie 3 Elemente zur Auswahl, die Dritte 2 Elemente, und so weiter. so Ihr code ausgeführt wird, 4! Berechnungen. Dies wird weiter unten erläutert

First iteration:
wählen Sie ein Zeichen aus {a,b,c,d}

Second Iteration:
wählen Sie ein Zeichen aus abgezogen Menge {{a,b,c,d} - {x}}, wobei x für den char gewählt aus der ersten iteration. also wenn 'ein' wählen Sie in der ersten iteration, diese iteration hat {b,c,d} zu wählen.

Third Iteration:
wählen Sie ein Zeichen aus abgezogen Menge {{a,b,c,d} - {x,y}}, wobei x und y gewählt werden chars aus den vorherigen Iterationen. d.h. wenn " a " ausgewählt wird bei der ersten iteration, und 'c' gewählt wird aus der 2. haben wir {b,d}, hier zu spielen.

Wiederholt dies, bis wir wählen 4 chars insgesamt. Einmal wählen wir 4 möglich, char, drucken wir die chars. Dann backtrack und wählen Sie einen anderen char aus der möglichen gesetzt. d.h. beim ansetzen der Dritten iteration wählen wir als Nächstes aus dem möglichen set {b,d}. Auf diese Weise erzeugen wir alle möglichen Permutationen der angegebenen Zeichenfolge.

Tun wir dieses set Manipulationen, so dass wir nicht die Auswahl die gleichen chars doppelt. also abcc, abbc, abbd,bbbb, sind ungültig.

Die swap-Anweisung in deinem code wird dieser Satz Bau. Es teilt die Zeichenfolge in zwei Sätze free set wählen Sie aus used set bereits verwendet. Alle chars auf der linken Seite des i+1 ist used set und rechts sind free set. In der ersten iteration, Sie haben die Wahl unter {a,b,c,d} und dann übergeben {a}:{b,c,d} sein, um die nächste iteration. Die nächste iteration wählt man {b,c,d} und übergibt {a,b}:{c,d} sein, um die nächste iteration, und so weiter. Wenn die Kontrolle backtracks zurück zu dieser iteration, Sie werden dann wählen Sie c Konstrukt und {a,c}, {b,d} mit tauschen.

Das ist das Konzept. Andernfalls ist die Rekursion einfach hier mit n tief und jedes level läuft eine Schleife für n, n-1, n-2, n-3...2,1 mal.

InformationsquelleAutor Sureshkumar T

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.