¿Cómo funciona el ciclo for de este algoritmo?

Ese método imprime todas las permutaciones posibles de los caracteres contenidos en una Cadena. Debe usarse de esta manera: permutación (“”, “ABCDE”). ¡Imprimiría los 5! cadenas que contienen los caracteres A, B, C, D y E.

(Si sabe lo que es una permutación, omita esto) Una permutación de un conjunto significa un posible orden en el que podemos colocar los objetos de un conjunto. Por ejemplo, si S = {A, B, D} , una posible ordenación es ABD, otra es ADB, otra es BDA y así sucesivamente.

En cada llamada recursiva, el algoritmo agrega un carácter de palabra a permanente , luego llama al método de permutación eliminando el carácter que se acaba de agregar (línea 4) para evitar ese carácter en llamadas adicionales (porque se agregó en permanente y no debe ser repetido). Como estamos eliminando caracteres de la palabra variable cada vez, cuando está vacío (línea 2), entonces podemos imprimir perm, porque perm debe tener todos los caracteres que se eliminaron anteriormente.

Nota: System.err.println debe usarse para imprimir errores, por lo que sugeriría cambiarlo a System.out.println.

Comience con una definición de una lista de permutaciones para una palabra dada. Se puede definir inductivamente.

1. La palabra vacía solo tiene una permutación: cadena vacía.
2. Todas las permutaciones para palabras no vacías pueden construirse agregando cada letra de la palabra al frente de todas las permutaciones para una palabra con esa letra eliminada.

Omitiré el “por qué” que son todas las permutaciones (es decir, no hay más permutaciones, solo aquellas descritas por esa definición).

Este algoritmo puede ser descrito por (un boceto; no he compilado esto para verificar):

permutaciones privadas de lista estática (palabra de cadena) {
Lista all = new ArrayList <> (); // todas las permutaciones …
if (word.isEmpty ()) {// la palabra vacía solo tiene una permutación: cadena vacía
all.append (“”);
devolver todo;
}
for (int i = 0; i char head = word.charAt (i); // …cada letra…
Cadena newword = word.substring (0, i) + word.substring (i + 1); // … una palabra con esa letra eliminada.
for (String p: permutations (newword)) {// … todas las permutaciones …
all.append (cabeza + p); // añadiendo … delante de …
}
}
devolver todo;
}

Ahora, esta solución obviamente coincide con la definición, así que la llamaré canónica. Sin embargo, obviamente requiere almacenar todas las permutaciones en la memoria, lo que en la práctica puede ser costoso para palabras grandes. Una mejor solución sería usar un iterador, de modo que la persona que llama podría causar que se produzcan permutaciones cuando sea necesario, luego consumir cada permutación y luego es su responsabilidad almacenarla (consumir memoria) o descartarla (no consumirla). memoria). No mostraré la solución con el iterador, porque necesito mostrar cómo llegar al algoritmo en cuestión.

El algoritmo en cuestión no está utilizando el iterador y no está exponiendo las permutaciones a la persona que llama. Pero tampoco está acumulando todas las permutaciones en la memoria. El algoritmo en cuestión difiere del algoritmo canónico al pasar la parte principal de las permutaciones de forma recursiva. Entonces, en lugar de que la persona que llama prefija las permutaciones con head (la parte head + p en la línea 11), la persona que llama modificará la cabeza (perm + word.charAt (i) es realmente perm + head) y prefijará las permutaciones (optimizadas en el caso de la palabra de longitud cero: el caso en la línea 4 en la implementación canónica realmente sería head + “”, pero agregar la cadena vacía no modifica la cadena, por lo que puede usar head tal como está: el algoritmo en cuestión genera el permanente, o la parte de la cabeza acumulada de la permutación sin modificar).

Ahora puedo responder a la pregunta de qué hace el bucle for: el bucle for construye un nuevo prefijo para las permutaciones de la palabra más corta y lo pasa a la función de permutación para que se incluya delante de las permutaciones de la palabra más corta.

Esta es una función recursiva que opera sacando un carácter de la cadena y colocándolo en la ranura número i , y luego recursivo.

Pasemos por esto.

Llamamos a esta función con

permutación (“”, “abcd”)

En la primera llamada, vamos a extraer cada carácter de la cadena. Entonces nos ramificamos así:

• “A” + permutaciones de bcd
• “B” + permutaciones de acd
• “C” + permutaciones de abd
• “D” + permutaciones de abc

Ahora vamos un paso más profundo. En el segundo nivel de recursión, nuevamente vamos a extraer un carácter del resto de la cadena, agregarlo a la permanente del prefijo y luego recurrir.

• “A” + permutaciones de bcd

• “Ab” + permutaciones de cd
• “Ac” + permutaciones de bd
• “Ad” + permutaciones de bc

• “Ba” + permutaciones de cd
• “Bc” + permutaciones de anuncio
• “Bd” + permutaciones de ac

• “Ca” + permutaciones de bd
• “Cb” + permutaciones de anuncio
• “Cd” + permutaciones de ab

• “Da” + permutaciones de bc
• “Db” + permutaciones de ac
• “Dc” + permutaciones de ab

Ahora el tercer nivel. Arranque un carácter del resto, agréguelo a la permanente del prefijo y repita el resto. (Solo voy a hacer algunos de estos. Pero si alguien quiere darme una edición sugerida con el resto completado, adelante).

• “A” + permutaciones de bcd

• “Ab” + permutaciones de cd

• “Abc” + permutaciones de d -> imprime “abcd”
• “Abd” + permutaciones de c -> imprime “abdc”

• “Acb” + permutaciones de d -> print “acbd”
• “Acd” + permutaciones de b -> print “acdb”

• “Adb” + permutaciones de c -> print “adbc”
• “Adc” + permutaciones de b -> imprime “adcb”

• “Ba” + permutaciones de cd
• “Bc” + permutaciones de anuncio
• “Bd” + permutaciones de ac

• “Ca” + permutaciones de bd
• “Cb” + permutaciones de anuncio
• “Cd” + permutaciones de ab

• “Da” + permutaciones de bc
• “Db” + permutaciones de ac
• “Dc” + permutaciones de ab

En el siguiente nivel, nuevamente sacamos un personaje de él. Obtendremos algo así como acbd + permutaciones de “” . Después de eso, veremos nuestro caso base e imprimiremos acbd.

1. “” + Permutaciones de abcd ->
2. “A” + permutaciones de bcd ->
3. “Ab” + permutaciones de cd ->
4. “Abc” + permutaciones de d ->
5. “Abcd” + permutaciones de “”
6. -> imprimir “abcd”

Es muy probable que haya escrito mal algo en los pasos recursivos a continuación. ¡Corrija si es así!

¿Por qué dices que no tiene sentido?

No necesita un depurador para comprender este elegante algoritmo recursivo; solo mira el globo y describe en inglés lo que hace.

• Toma una cadena de inicio permanente (presumiblemente vacía en la llamada inicial), y agrega cada carácter de palabra a su vez.
• Luego, a cada cadena alargada (por el carácter elegido), se llama a sí misma en la palabra acortada (con el carácter elegido eliminado).
• El caso base es cuando todos los caracteres se han tomado de la palabra, y luego se imprime la cadena de resultados.

Vea cómo funciona esto para la permutation(“”,”abc”) ; la sangría refleja la profundidad de recursión:

llamada más externa
“” + “a”, luego “a”, “bc”:
“a” + “b”, luego “ab”, “c”:
“ab” + “c”, luego “abc”, “” (caso base); imprimir “abc”
“a” + “c”, luego “ac”, “b”:
“ac” + “b”, luego “acb”, “” (caso base); imprimir “acb”
“” + “b”, luego “b”, “ac”:
“b” + “a”, luego “ba”, “c”:
“ba” + “c”, luego “bac”, “” (caso base); imprimir “bac”
“b” + “c”, luego “bc”, “a”:
“bc” + “a”, luego “bca”, “” (caso base); imprimir “bca”
… y así

Puede ver intuitivamente cómo funciona esto; las permutaciones de una palabra toman cada carácter [math] c [/ math] de la palabra, alternando [math] c [/ math] a todas las permutaciones de la palabra con [math] c [/ math] eliminado.

Este es un buen ejemplo de cómo el código imperativo ofusca lo que está sucediendo al introducir conceptos y mecanismos irrelevantes (el bucle, la variable, separando una cadena tediosamente mediante indexación). La misma idea expresada en Scala (con pequeños cambios en los tipos):

permisos permanentes (palabra: Set [Char]): Set [List [Char]] =
if (word.isEmpty) Set (List ()) // caso base; una permutación vacía
más word.flatMap (c => permisos (word-c) .map (c :: _))

Correr:

scala> perms (“abcd” .toSet)
res1: Set [List [Char]] = Set (List (b, d, c, a), List (c, a, d, b), List (b, c, d, a), List (d, b , c, a), Lista (c, a, b, d), Lista (c, b, d, a), Lista (a, b, c, d), Lista (d, c, a, b), Lista (a, d, c, b), Lista (b, d, a, c), Lista (c, b, a, d), Lista (d, a, b, c), Lista (b, c, a, d), Lista (b, a, c, d), Lista (c, d, b, a), Lista (a, b, d, c), Lista (d, c, b, a), Lista (c, d, a, b), Lista (d, a, c, b), Lista (b, a, d, c), Lista (a, c, d, b), Lista (a, d, b , c), Lista (a, c, b, d), Lista (d, b, a, c))

scala> perms (“abcd” .toSet) .size
res2: Int = 24

Esto imprime todas las permutaciones posibles de la palabra de entrada de forma recursiva (suponiendo que la primera vez que llamamos a la función, perm es la cadena vacía).

El bucle for pasa sobre todos los caracteres posibles que quedan por elegir. Luego llamamos a la misma función, con el carácter i-ésimo agregado al final de nuestra permutación.

También eliminamos ese carácter de la cadena de posibles caracteres para elegir. Esto se hace tomando la subcadena de todo antes del i-ésimo carácter y agregándolo a la subcadena de todo después del i-ésimo carácter. Que luego se convierte en la nueva entrada para Word.

Creo que la complejidad temporal de esto será O (n * n!). Podría reducirse a O (n!) Con un poco más de trabajo, que es el mejor caso si realmente desea imprimir cada permutación.

Pero también tenga en cuenta que si un carácter aparece varias veces en la palabra, imprimiremos múltiples copias de la misma permutación. (En el peor de los casos, nuestra palabra de entrada podría tener n copias del mismo carácter, e imprimiríamos la misma palabra n! Veces). Probablemente no sea intencional; un algoritmo mejor podría garantizar que eso no suceda.

¡Este es un árbol que representa las llamadas realizadas por el bucle for dentro de cada llamada recursiva de la función de permutación! Espero que ayude 🙂