hoán vị chuỗi trong Java (không đệ quy)

Question

Tôi là một học sinh trung học lớp 10 đang cố gắng làm việc thông qua một số vấn đề trong cuốn sách Cấu trúc và Thuật toán dữ liệu trên Java.

Một trong những câu hỏi là in tất cả các hoán vị của một chuỗi.

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

Đây là nỗ lực của tôi. Cuốn sách yêu cầu tôi làm điều đó cho các ký tự 'c', 'a', 'r', 'b', 'o', 'n'. Giải pháp của tôi chỉ làm như vậy, nhưng khi tôi cố gắng sử dụng 3 hoặc 4 từ chữ cái, nó cho tôi sự lặp lại. Nếu tôi loại bỏ vòng ngoài cùng và cố gắng in nó, nó hoạt động cho 3 và 4 từ chữ nhưng không phải cho từ 5 chữ cái.

Tôi rất vui khi làm rõ lý do của tôi, tôi biết nó không hiệu quả nhất, nhưng hãy nhớ rằng tôi chỉ học lớp 10 và đây là điều tôi nghĩ đến trước tiên.

Ai đó có thể vui lòng giúp tôi hoặc ít nhất là gợi ý điều gì sai? Xin vui lòng không tư vấn cho một giải pháp đệ quy, bởi vì tôi muốn làm việc thông qua nó lặp đi lặp lại đầu tiên. Cảm ơn, Sumit.

Answer 1

Hoán vị lặp lại

Khi bạn có nhiều thứ để lựa chọn ... bạn có lựa chọn n mỗi lần!

Khi chọn r trong số họ, các hoán vị là:

n × n × ... (lần r) = n^r

tôi trình bày 2 trường hợp. Trường hợp đầu tiên là khi chúng ta biết kích thước của n và r đã có, và nó dễ dàng. Thứ hai khi n và r là động.

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