Permutacja tablicy, z powtórzeniami, w Javie

Question

Jest kilka podobnych pytań na stronie, które pomogły, ale nie jestem w stanie całkowicie rozwiązać problemu, więc mam nadzieję, że to nie będzie powtarzalne.

Jest to zadanie domowe, w którym masz zestaw tablic znaków [A, B, C] i musisz używać rekursji, aby uzyskać wszystkie permutacje (z powtórzeniami). Kod mam jakby to robi:

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

Jednak parametr n powinien określić długość wyjścia, więc gdy ta funkcja wypisuje wszystkie permutacje długości 3, nie można zrobić je o długości 2. I próbowałem wszystkiego, co przychodzi mi do głowy, i przeszukałem wyniki wyszukiwania Google, i jestem pogrążony we własnej osobie, że nie jestem w stanie rozwiązać problemu, który wydaje się dość prosty.

Answer 1

Jeśli dobrze rozumiem , dostaniesz zestaw znaków c i żądaną długość n.

Technicznie nie ma czegoś takiego jak permutacja z powtórzeniem. Zakładam, że chcesz wszystkie ciągi o długości n z literami od c.

Można zrobić to w ten sposób:

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 

w postaci kodu:

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

Po prostu wpadłem na pomysł. Co jeśli dodałeś ukrytą literę (H dla ukrytego) [A, B, C, H], a potem zrobiłeś wszystkie permutacje o stałej długości (powiedziałeś, że wiesz jak to zrobić). Następnie, po jej przeczytaniu, zatrzymujesz się na ukrytej postaci, np. [B, A, H, C] staną się (B, A).

Hmm, minusem jest to, że trzeba by śledzić te, które zostały utworzone chociaż [B, H, A, C] jest taka sama jak [B, H, C, A]

Answer 3

Tutaj jest C# w wersji do generowania permutacji danego łańcucha z powtórzeń:

(Zasadnicza idea jest - liczba permutacji ciągu o długości 'n' z powtórzeniami wynosi 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); 
      } 
     } 

Poniżej są odpowiednie testy jednostkowe:

[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

stosować ten javy realizacji permutacji z powtórzeniami. A ~ (n, m): n = długość tablicy, m = k. m może być większe lub mniejsze niż n.

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

} 

Przykâadowa jest

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