Generieren aller Permutationen einer bestimmten Länge

Question

Angenommen, wir haben ein Alphabet "abcdefghiklimnop". Wie kann ich rekursiv Permutationen mit Wiederholung dieses Alphabets in Gruppen von FIVE effizient erzeugen?

Ich habe mit diesen ein paar Tagen jetzt gekämpft. Jede Rückmeldung wäre hilfreich.

Das ist im Wesentlichen die gleiche wie: Generating all permutations of a given string

Allerdings habe ich nur die Permutationen in Längen von fünf des gesamten String will. Und ich konnte das nicht herausfinden.

SO für alle Teilstrings der Länge 5 von "abcdefghiklimnop", finden Sie die Permutationen der Teilkette. Zum Beispiel, wenn die Teilzeichenfolge abcdef wäre, würde ich alle Permutationen davon wollen, oder wenn die Teilzeichenfolge defli wäre, würde ich alle Permutationen dieser Teilzeichenfolge wollen. Der Code unten gibt mir alle Permutationen eines Strings, aber ich würde gerne alle Permutationen aller Teilstrings der Größe 5 eines Strings finden.

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

Um fünf Zeichen aus einem String rekursiv auszuwählen, folgen einem einfachen Algorithmus:

• Ihre Methode sollte einen Teil bekommt in so weit gefüllt, und die erste Position in der fünfstelligen Permutation das braucht ein Zeichen
• Wenn die erste Position, die ein Zeichen braucht, über fünf ist, sind Sie fertig; drucken Sie die Kombination, die Sie so weit haben, und zurück
• Andernfalls setzen jedes Zeichen in der aktuellen Position in der Permutation und machen einen rekursiven Aufruf

Dieses viel kürzer in Java ist:

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

der Anrufer steuert die gewünschte Länge der Permutation durch die Anzahl der Elemente in wechselnden perm:

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

Demo.

Answer 2

Alle Permutationen von fünf Zeichen werden in der Menge der ersten fünf Zeichen jeder Permutation enthalten sein. Zum Beispiel können, wenn Sie alle zwei Zeichen Permutationen einer Zeichenkette vier ‚abcd‘ wollen Sie sie aus allen Permutationen erhalten: ‚abcd‘, ‚abdc‘, ‚acbd‘, ‚ACDB‘ ... ‚dcba‘

Anstatt sie in Ihrer Methode zu drucken, können Sie sie in einer Liste speichern, nachdem Sie überprüft haben, ob diese Permutation bereits gespeichert ist. Abhängig von Ihrer Spezifikation kann die Liste entweder an die Funktion oder an ein statisches Feld übergeben werden.

Answer 3

Dies kann leicht mit Bit-Manipulation erfolgen.

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