Iterative solution for :- Finding String permutations

Question

I read this simple and elegant python solution for finding all permutations of a given string. It is recursive. Based on that I tried to implement an iterative solution in python.

Below is my code. But it works only for 3 character strings :( Stuck trying to see how the recursion base case condition and recursion condition translates into iterative(non-recursive) Any pointers would help to get a iterative solution working.(Either based on this algorithm or any other)

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

You can convert every recursion to an iteration using a stack. But in this case it's even simpler since the algorithm is very simple.

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

For a more general conversion of recursion to iteration with a stack read this

• goldenmean: Thanks for the link which explained And for the solution.
• deeshank: perfect and neat!