Generowanie wszystkich permutacji o określonej długości

Question

Załóżmy, że mamy alfabet "abcdefghiklimnop". Jak rekurencyjnie generować permutacje z powtarzaniem tego alfabetu w grupach FIVE w efektywny sposób?

Walczę z tym od kilku dni. Wszelkie opinie będą pomocne.

Zasadniczo to jest takie samo jak: Generating all permutations of a given string

Jednakże, po prostu chcę permutacji o długości pięciu całego łańcucha. I nie udało mi się tego rozgryźć.

SO dla wszystkich podciągów o długości 5 "abcdefghiklimnop", znajdź permutacje podłańcucha. Na przykład, jeśli podciągu był abcdef, chciałbym wszystkie permutacje tego, lub jeśli substring był defli, chciałbym wszystkie permutacje tego podłańcucha. Poniższy kod daje mi wszystkie permutacje ciągu, ale chciałbym użyć do znalezienia wszystkich permutacji wszystkich podciągów o rozmiarze 5 ciągu.

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

Answer 1

Aby odebrać pięć znaków z ciągu rekurencyjnie, wykonaj prosty algorytm:

• Twoja metoda powinna dostać część wypełnionego tak daleko, a pierwsze miejsce w permutacji pięć znaków który potrzebuje znaku
• Jeśli pierwsza pozycja wymagająca postaci ma więcej niż pięć, oznacza to, że skończyłeś; wydrukować kombinację że masz tak daleko, i powrócić
• W przeciwnym razie, umieścić każdy znak w bieżącym położeniu w permutacji, i zrobić wywołanie rekurencyjne

To jest dużo krótszy w Java:

private static void permutation(char[] perm, int pos, String str) { 
    if (pos == perm.length) { 
     System.out.println(new String(perm)); 
    } else { 
     for (int i = 0 ; i < str.length() ; i++) { 
      perm[pos] = str.charAt(i); 
      permutation(perm, pos+1, str); 
     } 
    } 
} 

wywołujący reguluje żądaną długość permutacji przez zmianę liczby elementów w perm:

char[] perm = new char[5]; 
permutation(perm, 0, "abcdefghiklimnop"); 

Demo.

Answer 2

Wszystkie permutacje po pięć znaków będą zawarte w zestawie pierwszych pięciu znaków każdej permutacji. Na przykład, jeśli chcesz uzyskać wszystkie permutacje dwóch znaków czteroznakowego ciągu znaków "abcd", możesz je uzyskać ze wszystkich permutacji: 'abcd', 'abdc', 'acbd', 'acdb' ... 'dcba'

Dlatego zamiast drukować je w swojej metodzie, możesz je zapisać do listy po sprawdzeniu, czy ta permutacja jest już zapisana. Listę można przekazać do funkcji lub pola statycznego, w zależności od specyfikacji.

Answer 3

Można to łatwo zrobić za pomocą bitowej manipulacji.

private void getPermutation(String str, int length) 
     { 
      if(str==null) 
       return; 
      Set<String> StrList = new HashSet<String>(); 
      StringBuilder strB= new StringBuilder(); 
      for(int i = 0;i < (1 << str.length()); ++i) 
      { 
       strB.setLength(0); //clear the StringBuilder 
       if(getNumberOfOnes(i)==length){ 
        for(int j = 0;j < str.length() ;++j){ 
        if((i & (1 << j))>0){ // to check whether jth bit is set (is 1 or not) 
         strB.append(str.charAt(j)); 
        } 
       } 
       StrList.add(strB.toString()); 
       } 
      } 
      System.out.println(Arrays.toString(StrList.toArray())); 
     } 

    private int getNumberOfOnes (int n) // to count how many numbers of 1 in binary representation of n 
    { 
     int count=0; 
     while(n>0) 
     { 
     n = n&(n-1); 
      count++; 
     } 
     return count; 
    }