Pregunta Comprender la recursividad para generar permutaciones


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

32
2017-09-24 08:00


origen


Respuestas:


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: Call graph

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

48
2017-09-24 08:35



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

21
2017-09-24 08:09



Para usar la recursión de manera efectiva en el diseño, resuelves el problema asumiendo que ya lo has 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.


17
2017-09-24 16:42



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 ej. 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.

Por lo tanto, 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 del ciclo se repite 'n' veces para mostrar los caracteres del ejemplo "ABC", es decir 3. Total 6 veces (veces factoriales) entramos si 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.

enter image description here enter image description here

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


3
2017-10-03 03:28



enter image description here

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


2
2017-10-10 09:13



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 los confusos console.log líneas;

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:

enter image description here

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

También como parte de los programas recursivos:

enter image description here


0
2018-05-17 02:45