क्या यह पुनरावर्ती समाधान (ब्रैकेट प्रिंट करने के लिए) को पुनरावर्तक संस्करण में परिवर्तित करना संभव है?

Question

मुझे प्रिंटिंग टैग "<" और ">" प्रिंटिंग की विभिन्न भिन्नताओं को मुद्रित करने की आवश्यकता है, टैग को कितनी बार प्रदर्शित होना चाहिए और नीचे रिकर्सन का उपयोग करके पायथन में समाधान है।

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) 

मैं एक मुश्किल समय वास्तव में इस को समझने और एक पुनरावृत्ति संस्करण में इस कन्वर्ट करने के लिए कोशिश करना चाहते हो रहा है, लेकिन मैं किसी भी सफलता नहीं मिली है।

इस धागे के अनुसार: Can every recursion be converted into iteration? - ऐसा लगता है कि यह संभव होना चाहिए और एकमात्र अपवाद एकरमेन फ़ंक्शन प्रतीत होता है।

यदि किसी को ग्रहण में बनाए गए "स्टैक" को देखने के तरीके पर कोई सुझाव है - तो इसकी भी सराहना की जाएगी।

पीएस। यह होमवर्क प्रश्न नहीं है - मैं बस रिकर्सन-टू-इयरेशन रूपांतरण को बेहतर ढंग से समझने की कोशिश कर रहा हूं।

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

Answer 1

आपने बिना किसी स्टैक के ऐसा करने के बारे में पूछा।

इस एल्गोरिथ्म, पूरे समाधान अंतरिक्ष चलता है तो यह मूल संस्करणों की तुलना में थोड़ा अधिक काम करता है, लेकिन यह मूल रूप से इसी अवधारणा है:

• प्रत्येक स्ट्रिंग अपने व्याकरण में संभव प्रत्यय के एक पेड़ है
• के बाद से केवल दो टोकन हैं, यह एक द्विआधारी पेड़
• पेड़ की गहराई हमेशा रहेंगे ग * 2 है, तो ...
• वहाँ होना चाहिए 2 ** (ग * 2) पेड़
ऐसे पथ

चूंकि प्रत्येक पथ द्विआधारी निर्णयों का अनुक्रम है, इसलिए पथ 0 और 2 ** (सी * 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 2

मैं अपने कोड के रूप में मूलतः एक ही संरचना रखने के लिए, लेकिन कोई स्पष्ट ढेर समारोह 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 3

हां।

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

आउटपुट ऑर्डर अलग है, लेकिन परिणाम समान होना चाहिए।

Answer 4

सामान्य तौर पर, एक प्रत्यावर्तन कॉल की एक पेड़, जड़ मूल कॉल किया जा रहा है, और पत्तियों कॉल कि recurse नहीं है किया जा रहा है बनाता है।

एक अपमानजनक मामला तब होता है जब प्रत्येक कॉल केवल एक अन्य कॉल करता है, इस मामले में पेड़ एक साधारण सूची में खराब हो जाता है। पुनरावृत्ति में परिवर्तन तब एक स्टैक का उपयोग करके हासिल किया जाता है, जैसा कि @ जेरेम्याह द्वारा दिखाया गया है।

अधिक सामान्य मामले में, यहां, जब प्रत्येक कॉल एक कॉल से अधिक (कड़ाई से) प्रदर्शन करती है। आप एक असली पेड़ प्राप्त करते हैं, और इसलिए, इसे पार करने के कई तरीके हैं।

यदि आप एक स्टैक के बजाय कतार का उपयोग करते हैं, तो आप एक चौड़ाई-पहले ट्रैवर्सल कर रहे हैं। @Jeremiah ने एक ट्रैवर्सल प्रस्तुत किया जिसके लिए मुझे कोई नाम नहीं पता। सामान्य "रिकर्सन" ऑर्डर आमतौर पर एक गहराई-पहला ट्रैवर्सल होता है।

ठेठ प्रत्यावर्तन का मुख्य लाभ यह है कि ढेर की लंबाई के रूप में ज्यादा बढ़ने नहीं है, तो आप सामान्य रूप में के लिए लक्ष्य रखना चाहिए गहराई-प्रथम ... अगर जटिलता पराजित नहीं करता है आप :)

मैं एक वृक्ष के पहले ट्रैवर्सल को गहराई से लिखने की शुरुआत करता हूं, एक बार यह आपके एल्गोरिदम को अपनाने के बाद काफी सरल होना चाहिए।

संपादित करें:

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

ध्यान दें कि ढेर प्रबंधन थोड़ा के सूचकांक को याद करने की जरूरत के कारण जटिल है: के बाद से मैं कुछ समय के लिए किया था, मैं अजगर पेड़ Traversal लिखा था, यह विहित उदाहरण है बच्चा वर्तमान में हम जा रहे थे।

और गहराई-पहले के आदेश निम्नलिखित कलन विधि के अनुकूलन:

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)