迭代解决方案:- 查找字符串排列 [英] 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屋！