Permutaciones de cadenas en Java (no recursivas)

Question

Soy un estudiante de escuela secundaria de 10º grado que intenta resolver algunos problemas en un libro de Data Structures and Algorithms sobre Java.

Una de las preguntas es imprimir todas las permutaciones de una cadena.

class C14 
{ 
public static void main(char a[]) 
{ 
    // char[] a = {'c','a','r','b','o','n'}; 
    int c=0,w=0; 
    for(int q = 0;q<a.length;q++) 
    { 
     for(int i=0;i<a.length;i++) 
     { 
      for(int j=1;j<a.length;j++) 
      { 
       for(int k=1;k<a.length-1;k++) 
       { 
        for(int z=0;z<a.length;z++) 
        { 
         System.out.print(a[z]); 
         c++; 
        } 
        w++; 
        System.out.println(); 
        char p=a[k+1]; 
        a[k+1]=a[k]; 
        a[k]=p; 
       } 
       System.out.println(); 
      } 
      System.out.println(); 
      char x=a[0]; 
      a[0]=a[1]; 
      a[1]=x; 
     } 
     } 
    System.out.println(" Character count = " + c); 
    System.out.println(" Word count = " + w); 
    } 
} 

Este es mi intento. El libro me pide que lo haga para los caracteres 'c', 'a', 'r', 'b', 'o', 'n'. Mi solución hace exactamente eso, pero cuando trato de usar palabras de 3 o 4 letras, me da repeticiones. Si elimino el bucle más externo e intento imprimirlo, funciona para palabras de 3 y 4 letras, pero no para palabras de más de 5 letras.

Estaré encantado de aclarar mi razonamiento, sé que no es el más eficiente, pero tenga en cuenta el hecho de que solo estoy en el décimo grado y esto es lo que primero se me ocurrió.

¿Alguien puede por favor ayudarme, o al menos darme una pista de lo que está mal? Por favor, no aconseje una solución recursiva, porque quiero trabajar en ella iterativamente primero. Gracias, Sumit.

Answer 1

Permutación con repeticiones

Cuando tiene n cosas para elegir ... n tiene opciones cada vez!

Al elegir r de ellas, las permutaciones son:

n × n × ... (r veces) = n^r

que estoy presentando 2 casos. El primer caso es cuando ya sabemos el tamaño de nyr, y es el más fácil. El segundo cuando n y r son dinámicos.

//when n and r are known statically 

class Permutation 
{ 
    public static void main(String[] args) 
    { 
     char[] values = {'a', 'b', 'c', 'd'}; 
     int n = values.length; 
     int r = 2; 

     int i = 0, j = 0; 
     for(i=0; i<n; i++) 
     { 
      for(j=0; j<n; j++) 
      { 
       System.out.println(values[j] + " " + values[i]); 
      } 
     } 
    } 
} 


//when n and r are known only dynamically 

class Permutation 
{ 
    public static void main(String[] args) 
    { 
     char[] values = {'a', 'b', 'c', 'd'}; 
     int n = values.length; 
     int r = 2; 
     int i[] = new int[r]; 
     int rc = 0; 
     for(int j=0; j<Math.pow(n,r); j++) 
     { 

      rc=0; 
      while(rc<r) 
      { 
       System.out.print(values[i[rc]] + " "); 
       rc++; 
      } 
      System.out.println(); 
      rc = 0; 
      while(rc<r) 
      { 
       if(i[rc]<n-1) 
       { 
        i[rc]++; 
        break; 
       } 
       else 
       { 
        i[rc]=0; 
       } 
       rc++; 
      } 
     } 
    } 
}