c++ - sintaxis - Comprender la recursividad para generar permutaciones

recursividad indirecta c++

Question

Encuentro recursividad, aparte de las más directas como factoriales, muy difíciles de entender. El siguiente fragmento imprime todas las permutaciones de una cadena. ¿Alguien puede ayudarme a entenderlo? ¿Cuál es el camino a seguir para comprender la recursión correctamente?

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

A pesar de que es una vieja pregunta y ya respondida, pensé en agregar mis aportes para ayudar a los nuevos visitantes. También planea explicar el tiempo de ejecución sin centrarse en la Reconciliación Recursiva.

He escrito la muestra en C # pero es fácil de entender para la mayoría de los programadores.

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

Pasos: por ejemplo, cuando pasamos la entrada como "ABC".

1. Método de permutaciones llamado desde Main por primera vez. Así que llamar con el índice 0 y esa es la primera llamada.
2. En la parte else en el ciclo for estamos repitiendo de 0 a 2 haciendo 1 llamada cada vez.
3. Debajo de cada ciclo estamos llamando recursivamente con LpCnt + 1. 4.1 Cuando el índice es 1, luego 2 llamadas recursivas. 4.2 Cuando el índice es 2, luego 1 llamadas recursivas.

Entonces, del punto 2 al 4.2 el total de llamadas es de 5 por cada bucle y el total es de 15 llamadas + llamada de entrada principal = 16. Cada vez que loopCnt es 3, entonces si se ejecuta la condición.

Del diagrama podemos ver que el recuento de bucles se convierte en 3 en total 6 veces, es decir, el valor factorial de 3, es decir, la longitud de entrada "ABC".

Si el enunciado for para bucle repite ''n'' veces para mostrar caracteres del ejemplo "ABC", es decir, 3. Total 6 veces (factoriales veces) entramos en si para mostrar las permutaciones. Entonces, el tiempo total de ejecución = n X n !.

He proporcionado algunas variables estáticas de CallCnt y la tabla para comprender la ejecución de cada línea en detalle.

Expertos, siéntanse libres de editar mi respuesta o comentario si alguno de mis detalles no es claro o incorrecto, estoy feliz de corregirlos.

Descargue el código de muestra y otras muestras de aquí

Answer 2

Elige a cada personaje de todos los caracteres posibles:

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

Me gustaría agregar mis 2 centavos aquí con la implementación de JavaScript. Puede navegar por los registros de la consola, así como también puede eliminar confusas líneas de console.log ;

let str = "ABC";

permute(str, 0, str.length - 1, 0);

function permute(str, left, right, depth) {
  console.log(
    "called by depth:",
    depth,
    "str:",
    str,
    "left:",
    left,
    "right:",
    right
  );
  if (left === right) {
    console.log("PRINT:", str + "/n");
  } else {
    for (let i = left; i <= right; i++) {
      str = swap(str, left, i);
      console.log(
        "swap:",
        str,
        "depth:",
        depth,
        "left:",
        left,
        "inner counter:",
        i
      );
      console.log(
        "call permute",
        "str:",
        str,
        "depth:",
        depth + 1,
        "start left:",
        str[left + 1],
        "until right:",
        str[right]
      );
      permute(str, left + 1, right, depth + 1);
      str = swap(str, left, i);
      console.log(
        "backtrack swap",
        "depth:",
        depth,
        "str:",
        str,
        "left:",
        left,
        "right:",
        i
      );
    }
  }
}

function swap(str, left, right) {
  let charArr = str.split("");
  let leftTemp = charArr[left];
  charArr[left] = charArr[right];
  charArr[right] = leftTemp;
  return charArr.join("");
}

SALIDA:

La imagen del árbol es de http://www.geeksforgeeks.org/write-ac-program-to-print-all-permutations-of-a-given-string/

También como parte de los programas recursivos:

Answer 4

Para utilizar la recursión de manera efectiva en el diseño, resuelve el problema asumiendo que ya lo ha resuelto . El trampolín mental para el problema actual es "si pudiera calcular las permutaciones de n-1 caracteres, entonces podría calcular las permutaciones de n caracteres eligiendo cada uno por turno y añadiendo las permutaciones de los n-1 caracteres restantes, que Estoy pretendiendo que ya sé cómo hacerlo ".

Entonces necesitas una forma de hacer lo que se llama "tocar fondo" en la recursión. Dado que cada nuevo sub-problema es más pequeño que el anterior, tal vez eventualmente llegue a un sub-sub-problema que REALMENTE sabe cómo resolver.

En este caso, ya conoce todas las permutaciones de UN carácter: es solo el personaje. Entonces sabes cómo resolverlo para n = 1 y para cada número que es uno más que un número puedes resolverlo, y listo. Esto está muy relacionado con algo llamado inducción matemática.

Answer 5

PaulR tiene la sugerencia correcta. Debe ejecutar el código "mano" (utilizando las herramientas que desee, depuraciones, papel, llamadas a función de registro y variables en ciertos puntos) hasta que lo comprenda. Para una explicación del código, lo referiré a la excelente respuesta de cuasiverse.

Quizás esta visualización del gráfico de llamadas con una cadena ligeramente más pequeña hace que sea más obvio cómo funciona:

El gráfico fue hecho 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 6

Este código y referencia pueden ayudarte a entenderlo.

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

Referencia: Geeksforgeeks.org