Permutationen Rekursion

Habe ich eine Zuweisung: Benutzer gibt einen String ein, z.B. ABCD und das Programm hat heraus zu geben, alll die Permutationen.
Ich möchte nicht den ganzen code nur ein Tipp. dies ist, was ich habe, so weit in thery habe ich nichts umgesetzt.

Wobei ABCD ein Beispiel:

Holen Fakultät der Länge der Zeichenfolge in diesem Fall 4! = 24.

24/4 = 6, Also den ersten Buchstaben zu ändern hat, nach 6. so weit so gut.

als Fakultät der übrigen Briefe, die drei 3! = 6.

6/3 =2 2 stellen für jeden Brief. von hier aus weiß ich nicht, wie kann es weiter zu füllen, 24 stellen.

Mit diesem Algorithmus werde ich alles haben, ist

ABCD

ABD

. (weiter mit 6 C-und 6 D)

Ich denke, mein problem ist, ich habe nicht viel Erfahrung mit rekursive Probleme so wer kann vorschlagen, einige Programme zu Programmieren, um mir helfen zu wissen, Rekursion besser bitte nicht.

Dank! Wenn irgendwas nicht verständlich ist, bitte darauf hinweisen.

Danke! Sie bedeutete, wie dieses Recht?
Permutations.java
Ja, es ändern können, ein kleines Beispiel einer permutation ist die Eingabe ABC - das sind die Permutationen ABC,ACB,BAC,BCA,CAB,CBA.

InformationsquelleAutor John Smith | 2011-03-25

4

Du hast Recht, dass die Rekursion ist der Weg zu gehen. Das Beispiel, das Sie gearbeitet thru w/das bisschen Mathe war alles richtig, aber auch irgendwie indirekt.

Hier einige pseudocode:
```
 def permute(charSet, soFar):
     if charSet is empty: print soFar //base case
     for each element 'e' of charSet:
         permute(charSet without e, soFar + e)  //recurse
```
Beispiel der teilweisen Rekursion tree
```
                      permute({A,B,C}, '')
                   /           |           \
 permute({B,C}, 'A')  permute({A,C}, 'B')   permute({A,B}, 'C')   
                          /          \
               permute({A}, 'BC')    permute({C}, 'BA')
                       |
               permute({}, 'BCA')<---BASE CASE, print 'BCA'
```
BEARBEITEN

Behandeln wiederholte Zeichen ohne Duplizierung von Permutationen. Lassen Sie unique eine Funktion zu entfernen, wiederholt Elemente aus einer collection (oder string, mit dem behandelt wird, wie eine geordnete Zeichen-Sammlung-thru-Indizierung).

1) Speichern Sie die Ergebnisse (einschließlich der Duplikate), filtern Sie heraus, danach
```
 def permuteRec(charSet, soFar):
     if charSet is empty: tempResults.add(soFar) //base case
     for each element 'e' of charSet:
         permute(charSet without e, soFar + e)  //recurse

 global tempResults[]

 def permute(inString):
     permuteRec(inString, '')
     return unique(tempResults)

 print permute(inString)
```
2) Vermeiden Sie die Erzeugung von Duplikaten in den ersten Platz
```
 def permute(charSet, soFar):
     if charSet is empty: print soFar //base case
     for each element 'e' of unique(charSet):
         permute(charSet without e, soFar + e)  //recurse
```
- Können Sie erklären, ein wenig weiter, weil ich nicht verstehen Sie vollständig, so dass die Basis-Fall wird ein leerer string sein? meine Idee von der Basis Fall war beides leer und nur 1 Zeichen einer Zeichenkette.
- Mein Base case: wenn die Länge des Strings ist weniger als 2 drucken Sie 0 für eine leere Zeichenfolge ist, wird Dieselbe Zeichenfolge für einen 1 Zeichen string.
- auf die erste Ausschreibung charSet werden Sammlung, die alle n Elemente soFar leer. auf Basis Fällen charSet leer und der soFar enthält alle n-Elemente. soFar bestellt werden muss charSet werden können sortierte oder unsortierte
- ich habe nicht wirklich Folgen Sie Ihrer Idee von base case. welchen string meinst du wenn Sie sagen, 'Länge der Zeichenkette'?
- Vielen Dank für zu helfen, kennen Sie übungen zur Verbesserung der Rekursion?
- Die Zeichenfolge, die der Benutzer eingibt, wenn es nur ein Brief oder leer. Ich denke, ich bin auf der Suche auf dieses problem der falsche Weg.
- Vielen Dank für Ihre Hilfe! ich habe den Dreh hier, und hoffe, dass mit Ihren Anregungen zu verbessern wird in die Rekursion.
- Rekursion übungen - schreiben Sie eine rekursive Funktion factorial (dies ist tail-Rekursion, single Rekursion aufrufen, das geht auch iterativ),versuchen zu implementieren mergesort nach dieser (binäre rekursive) machen Sie sich vertraut mit Baum-Strukturen (es ist eine rekursive Struktur) und umsetzen. schreiben Sie etwas für die fibonacci-Folge. check-out im Zusammenhang mit Fragen auf der rechten Seite. fügen Sie den Ausdruck-Argumente am Anfang jeder Rekursion nennen, damit Sie Folgen können, wo die Rekursion geht (oder verwenden Sie sprachkonstrukt für einen stack-trace) und machen Sie sich vertraut mit dem stack. Sie Art brauchen, um zu bauen, eine intuition für Sie.
- Sie hatte nicht eine schlechte Idee, mit 'Der String, den der Benutzer eingibt, wenn es nur ein Buchstabe oder leer', aber denken Sie daran, es braucht nicht das zu sein, was die Eingabe des Benutzers, kann es mehrere Rekursion Schichten später. es muss nur das argument der Funktion.
- Was ist, wenn der Benutzer einen string, der enthält doppelte Zeichen, wie "AABC"?
- Der pseudocode, die ich ursprünglich gepostet hab oder nicht, betrachten Sie diese, und als solche ausgeben würde einige Duplikate. Es hat nicht allzu schwer zu handhaben, tho, ich habe zwei Möglichkeiten.
InformationsquelleAutor jon_darkstar
0

Machen, eine Methode, die einen string.

Wählen Sie einen Buchstaben aus dem string und der Ausgabe.

Erstellen Sie eine neue Zeichenfolge mit dem input-string minus den Brief, den Sie ausgewählt.

rufen Sie die oben genannte Methode mit der neuen Kette, wenn es mindestens 1 Zeichen

tun dies Kommissionierung von einem Buchstaben für jede mögliche Buchstaben.

InformationsquelleAutor MeBigFatGuy

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.

BEARBEITEN