mostrar - Imprime todas las permutaciones de una cadena en C
mostrar permutaciones en java (9)
¡El código que encontraste es correcto! El algoritmo intercambia el carácter actual en la cadena con todos los caracteres subsiguientes y llama recursivamente a la función. Es difícil de explicar con palabras. La siguiente figura puede ser de alguna ayuda para usted.
Se está realizando el backracking en el segundo swap para revertir el efecto del primer swap, es decir, volveremos a la cadena original y ahora intercambiaremos el siguiente carácter de la matriz con el carácter actual. La complejidad temporal del algo. es O (n * n!) ya que el bucle se ejecuta n veces y la función de permiso se llama n! veces. (Para la primera iteración, se llama n veces; para la segunda iteración (n-1) veces, etc.).
Fuente : http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
Estoy aprendiendo retroceso y recursión y estoy atascado en un algoritmo para imprimir todas las permutaciones de una cadena. Lo resolví utilizando el algoritmo de campana para la permutación, pero no puedo entender el método de recursión. Busqué en la web y encontré este código:
void permute(char *a, int i, int n)
{
int j;
if (i == n)
printf("%s/n", a);
else
{
for (j = i; j <= n; j++)
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j));
}
}
}
¿Cómo funciona básicamente este algoritmo que no puedo entender? Incluso he intentado correr en seco!
¿Cómo se aplica el seguimiento?
¿Y es más eficiente que el algoritmo de Bell para el cálculo de la permutación?
El código tiene 2 problemas , ambos relacionados con n , la longitud supuesta de la cadena. El código for (j = i; j <= n; j++) { swap((a+i), (a+j)); ... for (j = i; j <= n; j++) { swap((a+i), (a+j)); ... intercambie el carácter nulo de la cadena ''/0'' y proporcione resultados truncados en el código. Verifique el original (i == n) que debería ser (i == (n-1)) .
El backtracking se aplica llamando a swap() doble de efectivo deshaciendo su swap original.
El orden de complejidad es el mismo para el algoritmo de Bell.
#include <stdio.h>
void swap(char *a, char *b) { char t = *a; *a = *b; *b = t; }
void permute(char *a, int i, int n) {
// If we are at the last letter, print it
if (i == (n-1)) printf("%s/n", a);
else {
// Show all the permutations with the first i-1 letters fixed and
// swapping the i''th letter for each of the remaining ones.
for (int j = i; j < n; j++) {
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j));
}
}
}
char s[100];
strcpy(s, "ABCD");
permute(s, 0, strlen(s));
El algoritmo básicamente trabaja en esta lógica:
Todas las permutaciones de una cadena X son lo mismo que todas las permutaciones de cada carácter posible en X, combinadas con todas las permutaciones de la cadena X sin esa letra.
Es decir, todas las permutaciones de "abcd" son
- "a" concatenado con todas las permutaciones de "bcd"
- "b" concatenado con todas las permutaciones de "acd"
- "c" concatenado con todas las permutaciones de "malo"
- "d" concatenado con todas las permutaciones de "bca"
Este algoritmo, en particular, en lugar de realizar una recursión en subcadenas, realiza la recursión en su lugar en la cadena de entrada, sin utilizar memoria adicional para asignar subcadenas. El "retroceso" deshace los cambios en la cadena, dejándola en su estado original.
La recursión realmente lo simplifica:
public static void permutation(String str)
{
permutation("", str);
}
private static void permutation(String prefix, String str)
{
int n = str.length();
if (n == 0) {
System.out.println(prefix);
} else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}
Me encontré con el mismo problema al analizar la ejecución de este algoritmo de retroceso en GeeksForGeeks. Comprueba por ti mismo cómo se ejecuta. A veces los valores de impresión realmente ayudan a visualizar la ejecución del programa.
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 0 //////// l = 0 //////// r = 2 //////// string = ABC
permute(a, l+1, r); ==== Values send to permute i.e. string= ABC //////// (l+1) = 1 //////// r = 2
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 1 //////// l = 1 //////// r = 2 //////// string = ABC
permute(a, l+1, r); ==== Values send to permute i.e. string= ABC //////// (l+1) = 2 //////// r = 2
ABC
______________________________________________________________________
swap((a+l), (a+i));++++ Backtract swap //////// i= 1 //////// l = 1 //////// r = 2 //////// string = ABC
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
------------------------------END OF BACKTRACK--------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 2 //////// l = 1 //////// r = 2 //////// string = ACB
permute(a, l+1, r); ==== Values send to permute i.e. string= ACB //////// (l+1) = 2 //////// r = 2
ACB
______________________________________________________________________
swap((a+l), (a+i));++++ Backtract swap //////// i= 2 //////// l = 1 //////// r = 2 //////// string = ABC
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
------------------------------END OF BACKTRACK--------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
swap((a+l), (a+i));++++ Backtract swap //////// i= 0 //////// l = 0 //////// r = 2 //////// string = ABC
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
------------------------------END OF BACKTRACK--------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 1 //////// l = 0 //////// r = 2 //////// string = BAC
permute(a, l+1, r); ==== Values send to permute i.e. string= BAC //////// (l+1) = 1 //////// r = 2
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 1 //////// l = 1 //////// r = 2 //////// string = BAC
permute(a, l+1, r); ==== Values send to permute i.e. string= BAC //////// (l+1) = 2 //////// r = 2
BAC
______________________________________________________________________
swap((a+l), (a+i));++++ Backtract swap //////// i= 1 //////// l = 1 //////// r = 2 //////// string = BAC
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
------------------------------END OF BACKTRACK--------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 2 //////// l = 1 //////// r = 2 //////// string = BCA
permute(a, l+1, r); ==== Values send to permute i.e. string= BCA //////// (l+1) = 2 //////// r = 2
BCA
______________________________________________________________________
swap((a+l), (a+i));++++ Backtract swap //////// i= 2 //////// l = 1 //////// r = 2 //////// string = BAC
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
------------------------------END OF BACKTRACK--------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
swap((a+l), (a+i));++++ Backtract swap //////// i= 1 //////// l = 0 //////// r = 2 //////// string = ABC
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
------------------------------END OF BACKTRACK--------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 2 //////// l = 0 //////// r = 2 //////// string = CBA
permute(a, l+1, r); ==== Values send to permute i.e. string= CBA //////// (l+1) = 1 //////// r = 2
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 1 //////// l = 1 //////// r = 2 //////// string = CBA
permute(a, l+1, r); ==== Values send to permute i.e. string= CBA //////// (l+1) = 2 //////// r = 2
CBA
______________________________________________________________________
swap((a+l), (a+i));++++ Backtract swap //////// i= 1 //////// l = 1 //////// r = 2 //////// string = CBA
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
------------------------------END OF BACKTRACK--------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
swap((a+l), (a+i)); ~~~~ Forward swap the //////// i= 2 //////// l = 1 //////// r = 2 //////// string = CAB
permute(a, l+1, r); ==== Values send to permute i.e. string= CAB //////// (l+1) = 2 //////// r = 2
CAB
______________________________________________________________________
swap((a+l), (a+i));++++ Backtract swap //////// i= 2 //////// l = 1 //////// r = 2 //////// string = CBA
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
------------------------------END OF BACKTRACK--------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
swap((a+l), (a+i));++++ Backtract swap //////// i= 2 //////// l = 0 //////// r = 2 //////// string = ABC
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
------------------------------END OF BACKTRACK--------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
Pseudo código:
String permute(String a[])
{
if (a[].length == 1)
return a[];
for (i = 0, i < a[].length(); i++)
append(a[i], permute(a[].remove(i)));
}
# include <stdio.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 i, int n)
{
int j;
if (i == n)
printf("%s/n", a);
else
{
for (j = i; j <= n; j++)
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j)); //backtrack
}
}
}
/* Driver program to test above functions */
int main()
{
char a[] = "ABC";
permute(a, 0, 2);
getchar();
return 0;
}
I create more specific but not efficient Program for permutation for general string.
It''s work nice way.
//ubuntu 13.10 and g++ compiler but it''s works on any platform and OS
//All Permutation of general string.
#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
using namespace std;
int len;
string str;
void permutation(int cnum)
{
int mid;
int flag=1;
int giga=0;
int dead=0;
int array[50];
for(int i=0;i<len-1;i++)
{
array[50]=''/0'';
dead=0;
for(int j=cnum;j<len+cnum;j++)
{
mid=j%len;
if(mid==cnum && flag==1)
{
cout<<str[mid];
array[dead]=mid;
dead++;
flag=0;
}
else
{
giga=(i+j)%len;
for(int k=0;k<dead;k++)
{
if((array[k]==giga) && flag==0)
{
giga=(giga+1)%len;
}
}
cout<<str[giga];
array[dead]=giga;
dead++;
}
}
cout<<endl;
flag=1;
}
}
int main()
{
cout<<"Enter the string :: ";
getline(cin,str);
len=str.length();
cout<<"String length = "<<len<<endl;
cout<<"Total permutation = "<<len*(len-1)<<endl;
for(int j=0;j<len;j++)
{
permutation(j);
}
return 0;
}
def perms(s):
if len(s) < 1:
return [s]
ps = []
for i in range(0, len(s)):
head, tail = s[i], s[0:i] + s[i + 1:]
ps.extend([head + tailp for tailp in perms(tail)])
return ps