Comprendere la ricorsione per generare permutazioni

Question

Trovo la ricorsione, oltre a quelle molto dirette come fattoriale, molto difficile da capire. Il seguente frammento stampa tutte le permutazioni di una stringa. Qualcuno può aiutarmi a capirlo. Qual è la strada da percorrere per comprendere correttamente la ricorsione.

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

Answer 1

PaulR ha il giusto suggerimento. È necessario eseguire il codice "a mano" (usando gli strumenti che si desidera - debugger, carta, chiamate di funzioni di registrazione e variabili in determinati punti) finché non lo si capisce. Per una spiegazione del codice ti riferirò all'eccellente risposta di quasiverse.

Forse questa visualizzazione del grafico chiamata con una stringa leggermente più piccolo rende più evidente come funziona:

Il grafico è stato realizzato con 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)"]; 
} 

Answer 2

Si sceglie ogni carattere da tutti i possibili caratteri a sinistra:

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

Answer 3

Per utilizzare la ricorsione in modo efficace nel design, a risolvere il problema assumendo che hai già risolto. Il trampolino mentale per il problema corrente è "se potessi calcolare le permutazioni di n-1 caratteri, allora potrei calcolare le permutazioni di n caratteri scegliendo ognuno a turno e aggiungendo le permutazioni dei rimanenti n-1 caratteri, che Sto fingendo di sapere già come fare ".

Quindi hai bisogno di un modo per fare ciò che viene chiamato "toccare" la ricorsione. Dal momento che ogni nuovo sotto-problema è più piccolo dell'ultimo, forse alla fine si arriva a un sotto-sotto-problema che sai VERAMENTE come risolvere.

In questo caso, conosci già tutte le permutazioni di UN personaggio: è solo il personaggio. Quindi sai come risolverlo per n = 1 e per ogni numero che è più di un numero per cui puoi risolverlo, e il gioco è fatto. Questo è strettamente correlato a qualcosa chiamato induzione matematica.

Answer 4

Anche se è una domanda poco vecchia e ha già risposto pensato di aggiungere i miei input per aiutare i nuovi visitatori. Prevede anche di spiegare il tempo di esecuzione senza concentrarsi sulla riconciliazione ricorsiva.

Ho scritto l'esempio in C# ma è facile da capire per la maggior parte dei programmatori.

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

Passi: Per esempio quando passiamo input come "ABC".

1. Metodo di permessi chiamato da Principale per la prima volta. Quindi chiamare con l'indice 0 e questa è la prima chiamata.
2. Nella parte else di loop for ripetiamo da 0 a 2 effettuando 1 chiamata ogni volta.
3. Sotto ogni ciclo, stiamo chiamando ricorsivamente con LpCnt + 1. 4.1 Quando l'indice è 1 quindi 2 chiamate ricorsive. 4.2 Quando l'indice è 2 quindi 1 chiamate ricorsive.

Quindi dal punto 2 al 4.2 le chiamate totali sono 5 per ogni ciclo e il totale è di 15 chiamate + chiamata di ingresso principale = 16. Ogni volta che loopCnt è 3 allora se la condizione viene eseguita.

Dal diagramma si può vedere il conteggio dei loop che diventa 3 totale 6 volte, vale a dire il valore del fattore di 3 cioè la lunghezza di "ABC" di ingresso.

Se l'istruzione per il ciclo si ripete 'n' volte per visualizzare caratteri dall'esempio "ABC", ad esempio 3. Totale 6 volte (Tempi fattoriali) in cui immettere se visualizzare le permutazioni. Quindi il tempo di esecuzione totale = n X n !.

Ho dato alcune variabili CallCnt statiche e la tabella per capire ogni esecuzione di riga in dettaglio.

Esperti, sentitevi liberi di modificare la mia risposta o commento se qualcuno dei miei dettagli non è chiaro o errato, sono felice correggerli.

Download the sample code and other samples from here

Answer 5

Questo codice e riferimento potrebbe aiutare a capire esso.

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

Riferimento: Geeksforgeeks.org