Suche nach allen möglichen Kombinationen innerhalb eines Strings mit Permutation

Question

Ich habe derzeit zwei Methoden, die Rekursion verwendet, um mir alle möglichen Kombinationen eines gegebenen geben String, ich habe dazu mit Hilfe dieser answer. Also, wenn ich trat in die String und es gibt diese Kombinationen:

and 
adn 
dan 
dna 
nad 
nda 

aber ich will es alle möglichen Kombinationen der Rest zurückzukehren selbst ein/zwei Buchstaben in dieser Zeichenfolge wie folgt:

a 
n 
d 
an 
ad 
na 
nd 
etc... 

Something like this answer but in java

, die auch erwähnt antwort und verknüpft Powersets, die alle möglichen Teilmengen von a, b, c zeigte:

Wie Sie sehen es nicht die Kombinationen wieder wie

c,b,a 
c,a,b 
c,a 
.... 

nach vorne macht Hier ist der aktuelle Code, den ich habe, wo ich dies umsetzen möchte:

public void permutation(String str) { 

    permutation("", str); 
} 

private void permutation(String prefix, String str) { 

    int n = str.length(); 
    if (n == 0) myList.add(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

if (n == 0) myList.add(prefix); 

Diese Anweisung wurde nur hinzugefügt, wenn Sie alle verfügbaren Zeichen in str permutiert haben.

Wenn Sie entfernen die if (n == 0) es alle Präfixe a-an zu and hinzufügen werde, so würden Sie stattdessen verwenden:

private void permutation(String prefix, String str) { 
    int n = str.length(); 
    myList.add(prefix); 
    if(n > 0) { 
     for (int i = 0; i < n; i++) 
      permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)); 

    } 

Sie werden offensichtlich eine Reihe von Dubletten erhalten und möglicherweise eine leere Zeichenfolge als Ergebnis der Rekursion, aber es gibt eine Collection können Sie verwenden, die keine Duplikate erlaubt, oder Sie können überprüfen, ob es ein Duplikat vor dem Hinzufügen ist. Ich überlasse die Optimierung Ihnen.

Answer 2

Powerset wird Sie nicht zurückgeben, was Sie wollen. Dies liegt daran, dass der Satz {a, b, c}{b, a, c} entspricht und für andere Sets, die Sie haben möchten.

Sie können Ihren Algorithmus ändern, um alle möglichen Permutationen von jedem Satz zu erstellen. Dadurch erhalten Sie einige der Duplikate, so dass Sie sie im Set speichern können.

Answer 3

Eine Möglichkeit, über dieses Problem nachzudenken, besteht darin, alle binären Kombinationen der gegebenen Menge zu berücksichtigen.

Zum Beispiel, wenn der Satz in Frage {a, b, c}, dann werden alle binären Kombinationen (2^3 = 8):

000 = {} 
001 = {c} 
010 = {b} 
011 = {b,c} 
100 = {a} 
101 = {a, c} 
110 = {a, b} 
111 = {a, b, c} 

Sobald Sie diese Sets bauen, können Sie Verwenden Sie Rekursion, um die Kombinationen jedes Satzes zu erhalten.