Permutation eines Arrays, mit Wiederholung, in Java

Question

Es gibt einige ähnliche Fragen auf der Website, die eine Hilfe gewesen sind, aber ich kann dieses Problem nicht ganz festnageln, also hoffe ich, dass es sich nicht wiederholt.

Dies ist eine Hausaufgabe, in der Sie ein gesetztes Array von Zeichen [A, B, C] haben und Rekursion verwenden müssen, um alle Permutationen zu erhalten (mit Wiederholung). Der Code, den ich irgendwie haben tut dies:

char[] c = {'A', 'B' , 'C'}; 

public void printAll(char[] c, int n, int k) { 
    if (k == n) { 
     System.out.print(c); 
     return; 
    } 
    else { 
     for (int j = 0; j<n; j++) { 
     for (int m = 0; m<n; m++) { 
      System.out.print(c[k]); 
      System.out.print(c[j]); 
      System.out.print(c[m] + "\r\n"); 
     } 
     } 
    }   
    printAll(c, n, k+1);  
} 

Allerdings sollte der Parameter n die Länge der Ausgabe definieren, so, wenn diese Funktion alle Permutationen der Länge ausdruckt 3, ist es nicht sie der Länge 2 ich tun kann, Ich habe alles versucht, was mir einfällt, und habe mich mit den Google-Suchergebnissen beschäftigt, und ich ärgere mich, dass ich nicht in der Lage bin, ein scheinbar einfaches Problem zu lösen.

Answer 1

Wenn ich richtig verstehe , Sie erhalten eine Reihe von Zeichen c und die gewünschte Länge n.

Technisch gibt es keine Permutation mit Wiederholung. Ich nehme an, Sie wollen alle Zeichenfolgen der Länge n mit Buchstaben von c.

Sie können es auf diese Weise tun:

to generate all strings of length N with letters from C 
-generate all strings of length N with letters from C 
    that start with the empty string. 

to generate all strings of length N with letters from C 
    that start with a string S 
-if the length of S is N 
    -print S 
-else for each c in C 
    -generate all strings of length N with letters from C that start with S+c 

In Code:

printAll(char[] c, int n, String start){ 
    if(start.length >= n){ 
    System.out.println(start) 
    }else{ 
    for(char x in c){ // not a valid syntax in Java 
     printAll(c, n, start+x); 
    } 
    } 
} 

Answer 2

Ich hatte gerade eine Idee. Was ist, wenn Sie ein verstecktes Zeichen (H für versteckt) [A, B, C, H] hinzugefügt haben, dann haben Sie alle Permutationen mit fester Länge gemacht (Sie sagten, Sie wissen, wie man das macht). Wenn Sie es dann ablesen, hören Sie bei dem versteckten Zeichen auf, z. [B, A, H, C] würde (B, A) werden.

Hmm, ist der Nachteil, dass Sie müssten, welche Sie obwohl erstellt verfolgen [B, H, A, C] ist die gleiche wie [B, H, C, A]

Answer 3

Hier ist C# -Version die Permutationen von Strings mit Wiederholungen zu erzeugen:

(wesentliche Idee ist - Anzahl der Permutationen der Zeichenfolge der Länge 'n' mit Wiederholungen ist n^n).

string[] GetPermutationsWithRepetition(string s) 
     { 
      s.ThrowIfNullOrWhiteSpace("s"); 
      List<string> permutations = new List<string>(); 
      this.GetPermutationsWithRepetitionRecursive(s, "", 
       permutations); 
      return permutations.ToArray(); 
     } 
     void GetPermutationsWithRepetitionRecursive(string s, string permutation, List<string> permutations) 
     { 
      if(permutation.Length == s.Length) 
      { 
       permutations.Add(permutation); 
       return; 
      } 
      for(int i =0;i<s.Length;i++) 
      { 
       this.GetPermutationsWithRepetitionRecursive(s, permutation + s[i], permutations); 
      } 
     } 

Im Folgenden sind die entsprechenden Unit-Tests:

[TestMethod] 
     public void PermutationsWithRepetitionTests() 
     { 
      string s = ""; 
      int[] output = { 1, 4, 27, 256, 3125 }; 
      for(int i = 1; i<=5;i++) 
      { 
       s += i; 
       var p = this.GetPermutationsWithRepetition(s); 
       Assert.AreEqual(output[i - 1], p.Length); 
      } 
     } 

Answer 4

Ich benutze diese Java Realisierung von Permutationen mit Wiederholungen. A ~ (n, m): n = Länge der Anordnung, m = k. m kann größer oder kleiner als n sein.

public class Permutations { 


    static void permute(Object[] a, int k, PermuteCallback callback) { 
     int n = a.length; 

     int[] indexes = new int[k]; 
     int total = (int) Math.pow(n, k); 

     Object[] snapshot = new Object[k]; 
     while (total-- > 0) { 
      for (int i = 0; i < k; i++){ 
       snapshot[i] = a[indexes[i]]; 
      } 
      callback.handle(snapshot); 

      for (int i = 0; i < k; i++) { 
       if (indexes[i] >= n - 1) { 
        indexes[i] = 0; 
       } else { 
        indexes[i]++; 
        break; 
       } 
      } 
     } 
    } 

    public static interface PermuteCallback{ 
     public void handle(Object[] snapshot); 
    }; 

    public static void main(String[] args) { 
     Object[] chars = { 'a', 'b', 'c', 'd' }; 
     PermuteCallback callback = new PermuteCallback() { 

      @Override 
      public void handle(Object[] snapshot) { 
       for(int i = 0; i < snapshot.length; i ++){ 
        System.out.print(snapshot[i]); 
       } 
       System.out.println(); 
      } 
     }; 
     permute(chars, 8, callback); 
    } 

} 

Beispiel Ausgabe ist

aaaaaaaa 
baaaaaaa 
caaaaaaa 
daaaaaaa 
abaaaaaa 
bbaaaaaa 
... 
bcdddddd 
ccdddddd 
dcdddddd 
addddddd 
bddddddd 
cddddddd 
dddddddd