Python-Rekursions-Permutationen

Ich habe Schwierigkeiten, einen Permutationscode mit Rekursion zu machen. Dies ist vermutlich, um eine Liste zurück auf die Verwendung mit allen posible Position für jeden Brief zurückzugeben. So für das Wort cat es vermutlich zurückzukehren ['cat','act',atc,'cta','tca','tac'] . So weit ich das habe

 def permutations(s): lst=[] if len(s) == 1 or len(s) == 0 : # Return a list containing the string, not the string return [s] # Call permutations to get the permutations that don't include the # first character of s plst = permutations(s[1:]) print(plst) for item in plst: print (item) plst= permutations(s[1+1:]) # Now move through each possible position of the first character # and create a new string that puts that character into the strings # in plst for i in range(len(s)): pass # Create a new string out of item # and put it into lst # Modify for item in lst: print(index) 

Es gibt Schritte, aber ich bin nicht sicher, wie man sie benutzt

3 Solutions collect form web for “Python-Rekursions-Permutationen”

Sie wollen Rekursion machen, also müssen Sie zuerst herausfinden, wie die Rekursion funktionieren würde. In diesem Fall ist es folgendes:

 permutation [a,b,c,...] = [a + permutation[b,c,...], b + permutation[a,c,..], ...] 

Und als endgültige Bedingung:

 permutation [a] = [a] 

So spaltet die Rekursion die Liste in Sublisten auf, wobei jeweils ein Element extrahiert wird. Dann wird dieses Element der Vorderseite jeder der Permutationen der Unterliste hinzugefügt.

Also im Pseudocode:

 def permutation(s): if len(s) == 1: return [s] perm_list = [] # resulting list for a in s: remaining_elements = [x for x in s if x != a] z = permutation(remaining_elements) # permutations of sublist for t in z: perm_list.append([a] + t) return perm_list 

Hilft das?

Rekursiv, denke über den Basisfall und baue aus dieser Intuition.

1) Was passiert, wenn es nur ein Zeichen 'c' gibt? Es gibt nur eine Permutation dieses Elements, und so geben wir eine Liste zurück, die nur dieses Element enthält.

2) Wie können wir die nächste Permutation generieren? Hinzufügen eines zusätzlichen Buchstabens 'a' an allen möglichen Positionen in der vorherigen Permutation 'c' gibt uns 'ca', 'ac'.

3) Wir können weiterhin größere und größere Permutationen bauen, indem wir in jeder früheren Permutation ein zusätzliches Zeichen an allen möglichen Positionen hinzufügen.

Der folgende Code gibt eine Liste eines Zeichens zurück, wenn der String ein Zeichen oder weniger hat. Andernfalls generieren wir für alle Permutationen, die nicht das letzte Zeichen in der Zeichenkette s [-1] enthalten, einen neuen String für jede Position, an der wir dieses Zeichen einfügen und den neuen String an unsere aktuelle Liste der Permutationen anhängen können.

 def permutations(s): if len(s) <= 1: return [s] else: perms = [] for e in permutations(s[:-1]): for i in xrange(len(e)+1): perms.append(e[:i] + s[-1] + e[i:]) return perms 

Wenn du in rekursiver Funktion verloren bist, solltest du den Anrufbaum zeichnen. Die folgende Version (inspirierte @Ben-Antwort) behält die Eingabe-Reihenfolge (wenn die Eingabe in lexikographischer Reihenfolge ist, wird die Liste der Permutationen, '012' -> ['012', '021', '102', '120', '201', '210'] .

 def permut2(mystr): if len(mystr) <= 1: return [mystr] res = [] for elt in mystr: permutations = permut2(mystr.replace(elt, "")) for permutation in permutations: res.append(elt + permutation) return res 

Die folgende Version funktioniert für Strings und Listen, beachten Sie die Rekonstruktion Schritt ist nicht das gleiche:

 def permut(array): if len(array) == 1: return [array] res = [] for permutation in permut(array[1:]): for i in range(len(array)): res.append(permutation[:i] + array[0:1] + permutation[i:]) return res 

Als Übungen solltest du den Anrufbaum dieser Funktionen zeichnen, merkst du etwas?

  • Python: Rekursive Funktion, um die größte Zahl in der Liste zu finden
  • Lock-Kombinationen für dynamische Sperrgröße
  • Python recursion return Keine Typ
  • Python - Eigenschaftseinstellung aus der Liste verursacht maximale Rekursionstiefe überschritten
  • Notwendigkeit, Pyramiden-Dreieck auf Python neu zu erstellen
  • Baktracking-Funktion, die die Berechnung berechnet, überschreitet die maximale Rekursionstiefe
  • N-Queen-Backtracking in Python: Wie gibt man Lösungen zurück, anstatt sie zu drucken?
  • Ist es möglich, die Rekursion aus dieser Funktion zu entfernen?
  • Rekursionsfunktion in Python
  • Python Recursive Funktion für Collatz Conjecture
  • Iteration in Rekursion umwandeln
  • Python ist die beste Programmiersprache der Welt.