Iterative Lösung für: - Finden von String-Permutationen

Question

Ich lese this einfache und elegante Python-Lösung zum Finden aller Permutationen einer gegebenen Zeichenfolge. Es ist rekursiv. Darauf aufbauend habe ich versucht, eine iterative Lösung in Python zu implementieren.

Unten ist mein Code. Aber es funktioniert nur für 3-Zeichen-Strings :(Stuck versucht zu sehen, wie die Rekursion Base Case-Bedingung und Rekursion Bedingung in iterative (nicht-rekursive) übersetzt Any Pointer würde helfen, eine iterative Lösung arbeiten. (Entweder basierend auf diesem Algorithmus oder andere andere)

def permutations_iter(word): 
while True: 
    perms = [] 
    result = [] 

    char = word[0] 
    new_word = word[1:] 

    if len(new_word)==2: 
     perms = [new_word,''.join(reversed(new_word))] 

    for perm in perms: 
     #insert the character into every possible location 
     for i in range(len(perm)+1): 
      result.append(perm[:i] + char + perm[i:]) 
    return result 

    if len(new_word)==2: 
     break; 


    #example code to call this iterative function   
    print permutations_iter("LSE") 

Answer 1

Sie jede Rekursion zu einer Iteration mit einem Stapel umwandeln kann. Aber es ist in diesem Fall noch einfacher, da der Algorithmus ist sehr einfach.

def perms(word): 
    stack = list(word) 
    results = [stack.pop()] 
    while len(stack) != 0: 
     c = stack.pop() 
     new_results = [] 
     for w in results: 
      for i in range(len(w)+1): 
       new_results.append(w[:i] + c + w[i:]) 
     results = new_results 
    return results 

Für eine allgemeinere Umwandlung von Rekursion Iteration mit einem Stapel lesen this