Можно ли преобразовать это рекурсивное решение (в квадратные скобки) в итерационную версию?

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)

Мне трудно понять это по-настоящему, и я хочу попробовать преобразовать это в итеративную версию, но у меня ничего не получилось.

В соответствии с этим потоком: Может ли каждая рекурсия быть преобразована в итерацию? - похоже, что это возможно, и единственным исключением является функция Аккермана.

Если у кого-нибудь есть какие-либо советы о том, как увидеть «стек», поддерживаемый в Eclipse - это также будет оценено.

PS. Это не домашний вопрос - я просто пытаюсь лучше понять преобразование рекурсии в итерацию.

Редактировать Мэтью М. пример вывода для лучшей визуализации:

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

Answer 1

Я пытался сохранить в основном ту же структуру, что и ваш код, но использовал явный стек, а не вызовы функций для genBracketsHelper:

def genBrackets(c=1):
    # genBracketsStack is a list of tuples, each of which
    # represents the arguments to a call of genBracketsHelper
    # Push the initial call onto the stack:
    genBracketsStack = [(c, c, '')]
    # This loop replaces genBracketsHelper itself
    while genBracketsStack != []:
        # Get the current arguments (now from the stack)
        (r, l, currentString) = genBracketsStack.pop()
        # Basically same logic as before
        if l > r or r == -1 or l == -1:
            continue # Acts like return
        if r == l and r == 0:
            print currentString
        # Recursive calls are now pushes onto the stack
        genBracketsStack.append((r-1,l, currentString + '>'))
        genBracketsStack.append((r,l-1, currentString + '<'))
        # This is kept explicit since you had an explicit return before
        continue

genBrackets(4)

Обратите внимание, что преобразование, которое я использую, основано на том, что все рекурсивные вызовы находятся в конце функции; код был бы более сложным, если бы это было не так.

Answer 2

Вы спрашивали об этом без стека.

Этот алгоритм обходит все пространство решения, поэтому он выполняет немного больше работы, чем исходные версии, но в основном это та же концепция:

• каждая строка имеет дерево возможных суффиксов в вашей грамматике
• , поскольку существует только два токена, это двоичное дерево
• глубина дерева всегда будет 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

Answer 3

Как правило, рекурсия создает Дерево вызовов, корень которого является исходным вызовом, а листья - вызовами, которые не рекурсируются.

Вырожденный случай - это когда каждый вызов выполняет только один другой вызов, в этом случае дерево вырождается в простой список. Преобразование в итерацию затем просто достигается с помощью стека, как продемонстрировал @ Jeremiah.

В более общем случае, как здесь, когда каждый вызов выполняет более (строго), чем один вызов. Вы получаете настоящее дерево, и поэтому есть несколько способов пройти его.

Если вы используете очередь вместо стека, вы выполняете обход в ширину. @Jeremiah представил обход, для которого я не знаю имени. Типичный «рекурсивный» порядок - это обычно обход в глубину.

Основным преимуществом типичной рекурсии является то, что длина стека не увеличивается так сильно, поэтому вы должны стремиться к глубине в целом ... если сложность не сокрушает вас:)

Я предлагаю начать с написания первого обхода дерева по глубине, как только это будет сделано, адаптация его к вашему алгоритму должна быть довольно простой.

РЕДАКТИРОВАТЬ: Поскольку у меня было некоторое время, я написал Обход дерева Python, это канонический пример:

class Node:
  def __init__(self, el, children):
    self.element = el
    self.children = children

  def __repr__(self):
    return 'Node(' + str(self.element) + ', ' + str(self.children) + ')'

def depthFirstRec(node):
  print node.element

  for c in node.children: depthFirstRec(c)

def depthFirstIter(node):
  stack = [([node,], 0), ]

  while stack != []:
    children, index = stack.pop()

    if index >= len(children): continue
    node = children[index]

    print node.element

    stack.append((children, index+1))
    stack.append((node.children, 0))

Обратите внимание, что управление стеками немного усложняется из-за необходимости запоминать индекс дочернего элемента, который мы в данный момент посещали.

И адаптация алгоритма по порядку глубины:

def generateBrackets(c):
  # stack is a list of pairs children/index
  stack = [([(c,c,''),], 0), ]

  while stack != []:
    children, index = stack.pop()

    if index >= len(children): continue  # no more child to visit at this level
    stack.append((children, index+1))    # register next child at this level

    l, r, current = children[index]

    if r == 0 and l == 0: print current

    # create the list of children of this node
    # (bypass if we are already unbalanced)
    if l > r: continue

    newChildren = []
    if l != 0: newChildren.append((l-1, r, current + '<'))
    if r != 0: newChildren.append((l, r-1, current + '>'))
    stack.append((newChildren, 0))

Я только что понял, что хранение индекса немного "слишком" сложно, так как я никогда не захожу обратно. Таким образом, простое решение состоит в удалении элементов списка, которые мне больше не нужны, и обработке списка как очереди (на самом деле может быть достаточно стека)!

Это применимо с минимальным преобразованием.

def generateBrackets2(c):
  # stack is a list of queues of children
  stack = [[(c,c,''),], ]

  while stack != []:
    children = stack.pop()

    if children == []: continue  # no more child to visit at this level
    stack.append(children[1:])   # register next child at this level

    l, r, current = children[0]

    if r == 0 and l == 0: print current

    # create the list of children of this node
    # (bypass if we are already unbalanced)
    if l > r: continue

    newChildren = []
    if l != 0: newChildren.append((l-1, r, current + '<'))
    if r != 0: newChildren.append((l, r-1, current + '>'))
    stack.append(newChildren)

Answer 4

Да.

def genBrackets(c):
    stack = [(c, c, '')]
    while stack:
        right, left, currentString = stack.pop()
        if left > right or right == -1 or left == -1:
            pass
        elif right == left and right == 0:
            print currentString
        else:
            stack.append((right, left-1, currentString + '<'))
            stack.append((right-1, left, currentString + '>'))

Порядок вывода отличается, но результаты должны быть одинаковыми.