是否可以将此递归解决方案(打印括号)转换为迭代版本？

Question

考虑到标签出现的次数,我需要打印打印有效标签"<"和">"的不同变体,下面是使用递归的python中的解决方案.

def genBrackets(c):
    def genBracketsHelper(r,l,currentString):
        if l > r or r == -1 or l == -1:
            return
        if r == l and r == 0:
            print currentString
        genBracketsHelper(r,l-1, currentString + '<')
        genBracketsHelper(r-1,l, currentString + '>')
        return
    genBracketsHelper(c, c, '')

#display options with 4 tags     
genBrackets(4)

我很难真正理解这一点,并希望尝试将其转换为迭代版本,但我没有取得任何成功.

根据这个线程:每个递归都可以转换成迭代吗？ - 它看起来应该是可能的,唯一的例外似乎是Ackermann功能.

如果有人有关于如何查看Eclipse中维护的"堆栈"的任何提示 - 这也将不胜感激.

PS.这不是一个功课问题 - 我只是想更好地理解递归到迭代转换.

由Matthieu M.编辑,提供更好的可视化输出示例:

>>> genBrackets(3)
<<<>>>
<<><>>
<<>><>
<><<>>
<><><>

Answer 1

您询问如何在没有堆栈的情况下执行此操作。

该算法遍历整个解决方案空间，因此它比原始版本做了更多的工作，但基本上是相同的概念：

• 每个字符串在语法中都有一个可能的后缀树
• 因为只有两个标记，所以它是一棵二叉树
• 树的深度始终是 c*2，所以...
• 必须有 2**(c*2) 条路径穿过树

由于每条路径都是二进制决策序列，因此路径对应于 0 到 2**(c*2)-1 之间整数的二进制表示。

所以：只需循环这些数字，看看二进制表示是否对应于平衡字符串。:)

def isValid(string):
    """
    True if and only if the string is balanced.
    """
    count = { '<': 0, '>':0 }
    for char in string:
        count[char] += 1
        if count['>'] > count['<']:
            return False # premature closure

    if count['<'] != count['>']:
        return False # unbalanced
    else:
        return True


def genBrackets(c):
    """
    Generate every possible combination and test each one.
    """
    for i in range(0, 2**(c*2)):
        candidate = bin(i)[2:].zfill(8).replace('0','<').replace('1','>')
        if isValid(candidate):
            print candidate