迭代解决方案: - 查找字符串排列 [英] Iterative solution for :- Finding String permutations
问题描述
我读了这个简单和优雅的python解决方案,用于查找给定字符串的所有排列。这是递归的。基于此,我尝试在python中实现迭代解决方案。
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.
以下是我的代码。但它仅适用于3个字符串:(试图看看递归基本情况条件和递归条件如何转换为迭代(非递归)任何指针都有助于使迭代解决方案工作。(基于此算法或任何其他)
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")
推荐答案
可以每递归转换成使用堆栈的迭代。但在这种情况下它更简单,因为算法非常简单。
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
这篇关于迭代解决方案: - 查找字符串排列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!