2011-02-23 13 views
6

Necesito imprimir las diferentes variaciones de las etiquetas válidas de impresión "<" y ">" dado el número de veces que deben aparecer las etiquetas y debajo está la solución en python usando recursion.¿Es posible convertir esta solución recursiva (para imprimir corchetes) en una versión iterativa?

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) 

Estoy teniendo un tiempo difícil entender realmente esto y querer tratar de convertir esto en una versión iterativa, pero no he tenido ningún éxito.

Según esta conversación: Can every recursion be converted into iteration? - parece que debería ser posible y la única excepción parece ser la función de Ackermann.

Si alguien tiene algún consejo sobre cómo ver la "pila" mantenida en Eclipse, eso también sería de agradecer.

PS. Esta no es una pregunta para la tarea: solo trato de entender mejor la conversión de recursión a iteración.

Edición de Matthieu M. un ejemplo de salida para una mejor visualización:

>>> genBrackets(3) 
<<<>>> 
<<><>> 
<<>><> 
<><<>> 
<><><> 
+0

Ackermann se puede convertir en una estructura iterativa, como cualquier otra función recursiva, suponiendo que se trabaja en un lenguaje completo de Turing. –

+0

Puede lograr dicho algoritmo usando programación dinámica. No sabría cómo implementarlo en Python, así que si está interesado en una versión de estilo C, dígame y publicaré un código. Todas las combinaciones posibles de N par de corchetes, básicamente son todos los posibles árboles binarios con N nodos. Para construir todos esos árboles, primero debe ser capaz de construir todos los árboles posibles con 0..N-1 nodos, y luego tomar uno de esos árboles con X nodos (donde X está entre 0..N-1) y otro árbol con nodos Y (donde Y es igual a N-1-X) y añádales una raíz común. – Fede

+0

Gracias a todos por las respuestas, todos fueron muy útiles y la parte más difícil es tener que seleccionar "una" respuesta correcta. Voy con la respuesta de @ tangentstorm ya que fue la versión "iterativa" más fácil de entender para mí. – AlgoLearner

Respuesta

2

Ha preguntado acerca de cómo hacer esto sin una pila.

Este algoritmo paseos todo el espacio de la solución, por lo que lo hace un poco más de trabajo que las versiones originales, pero es básicamente el mismo concepto:

  • cada cadena tiene un árbol de posibles sufijos en su gramática
  • ya que sólo hay dos fichas, que es un árbol binario
  • la profundidad del árbol siempre será C * 2, así que ...
  • debe haber 2 ** (c * 2) rutas a través del árbol de

Como cada ruta es una secuencia de decisiones binarias, las rutas corresponden a las representaciones binarias de los números enteros entre 0 y 2 ** (c * 2) -1.

Así que simplemente recorra esos números y vea si la representación binaria corresponde a una cadena balanceada. :)

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 
+0

Buen enfoque - esto parece tan sencillo - es un poco triste que no fuera más obvio (con la condición de que necesito buscar las funciones bin y zfill) – AlgoLearner

4

Traté de mantener básicamente la misma estructura que el código, pero utilizando una pila explícita en lugar de llamadas de función a 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) 

Tenga en cuenta que la conversión que estoy utilizando depende de que todas las llamadas recursivas se encuentren al final de la función; el código sería más complicado si ese no fuera el caso.

+0

Excelente, gracias, esto definitivamente ayuda. También tengo curiosidad por saber si hay un método que no usa una pila. – AlgoLearner

+0

@AlgoLearner: Probablemente pueda usar un conjunto de variables globales para representar los parámetros y usar un contador para representar la profundidad de recursión, pero eso sería más complicado y menos general para otras funciones recursivas. –

+0

En realidad, después de un impulso también debe saltar al 'inicio'. Así que dos llamadas recursivas una tras otra no necesitan trasladarse a dos impulsos consecutivos ... –

0

Sí.

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 + '>')) 

El orden de salida es diferente, pero los resultados deben ser los mismos.

+0

Supongo que debería haber refrescado antes de publicar. :) Parece que mi conversión fue más o menos la misma que la de Jeremiah. Pregunta divertida! – tangentstorm

+0

Bueno, ¡entonces vote la pregunta! –

+1

Lo haré, pero no tengo suficientes votos para el día. :) – tangentstorm

1

En general, una recursión crea un árbol de llamadas, la raíz es la llamada original, y las hojas son las llamadas que no son recursivos.

Un caso degenerado es cuando cada llamada solo realiza otra llamada, en este caso el árbol degenera en una lista simple. La transformación en una iteración se logra simplemente utilizando una pila, como lo demuestra @Jeremiah.

En el caso más general, como aquí, cuando cada llamada realiza más (estrictamente) que una llamada. Obtienes un árbol real, y hay, por lo tanto, varias formas de atravesarlo.

Si utiliza una cola, en lugar de una pila, está realizando un recorrido transversal en anchura. @Jeremiash presentó un recorrido por el cual no conozco ningún nombre. El orden típico de "recursión" es normalmente un recorrido transversal en profundidad.

La principal ventaja de la recursividad típico es que la longitud de la pila no crece tanto, por lo que debe aspirar a primero en profundidad, en general, ... si la complejidad no abrumar a ti :)

Sugiero comenzar escribiendo un primer recorrido de profundidad de un árbol, una vez hecho esto, adaptarlo a su algoritmo debería ser bastante simple.

EDIT: Ya que tenía algún tiempo, me escribió el pitón del árbol de recorrido, es el ejemplo canónico:

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)) 

Tenga en cuenta que la gestión de la pila es algo complicado por la necesidad de recordar el índice de la niño que estábamos visitando actualmente.

y la adaptación del algoritmo siguiendo el orden de primero en profundidad:

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)) 

Me acabo de dar cuenta que el almacenamiento del índice es un poco "demasiado" complicado, ya que nunca visita de regreso. La solución simple consiste en eliminar los elementos de la lista que ya no necesito, tratando la lista como una cola (¡de hecho, una pila podría ser suficiente)!

Esto se aplica con una transformación mínima.

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) 
Cuestiones relacionadas