पायथन

Question

में कोष्ठक के वैध संयोजन को मुद्रित करना मैं अपने अंतर्ज्ञान का उपयोग करके अजगर में कोष्ठक के सभी मान्य संयोजन को मुद्रित करने का प्रयास कर रहा हूं। यह लगभग काम करता था लेकिन सिर्फ यह कि कुछ संयोजन मुद्रित नहीं करता है। कोड इस

solution = "" 

def parentheses(n): 

    global solution 

    if n == 0: 
     print solution 
     return 

    for i in range(1, n+1): 
     start_index = len(solution) 
     solution = solution + ("(" * i + ")" * i) 
     parentheses(n - i) 
     solution = solution[:start_index] 

if __name__ == "__main__": 
    n = int(raw_input("Enter the number of parentheses:")) 
    print "The possible ways to print these parentheses are ...." 
    parentheses(n) 

n = 3 के लिए की तरह लग रहा है, यह प्रिंट

()()()
() (())
(())()
((()))

यह इस तरह काम करता है।

पहले यात्रा में

()()(), प्रिंट किया जाएगा जब तत्काल माता-पिता के लिए कॉल रिटर्न, यह (सूची के स्लाइस होगा जहां यह पहले जो अब हो जाएगा संलग्न करने के लिए शुरू कर दिया) और पाश की अगले चरण चलाने मुद्रित करने के लिए() (()) और इतने

पर समस्या मैं किसी भी तरह इस तर्क

(()())

का उपयोग कर इस संयोजन पर कब्जा करने में सक्षम नहीं हूँ है

जबकि मैं इसे ठीक करने के बारे में सोच रहा हूं, अगर कोई पाइथो एन गुरु इस के लिए एक फिक्स का सुझाव दे सकते हैं, तो यह बहुत अच्छा होगा। वैकल्पिक समाधान हैं, लेकिन जब से मैं बहुत करीब आया, मैं अपनी सुधार करना चाहता हूं।

Answer 1

मुझे लगता है कि तर्क का आपका वर्तमान संस्करण सभी संभावनाओं को पकड़ने के लिए थोड़ा अधिक विस्तारित है।

1. हम अपने खोलने वाले कोष्ठक के सभी का उपयोग किया है और सिर्फ उन्हें
2. बंद करने के लिए हम किसी भी वर्तमान में खुले कोष्ठकों की जरूरत नहीं है और जोड़ने की जरूरत की जरूरत है:

   यह समस्या 3 अलग मामलों करने पर निर्भर करता

3. हमें बंद करने से पहले एक कम से कम एक खुला है और या तो एक नया या बंद कर सकता है।

उस तर्क का पालन करने के लिए, हम तो खुले कोष्ठक की संख्या हम उपयोग करने के लिए छोड़ दिया है (no नीचे), कोष्ठक की वर्तमान स्ट्रिंग, और खुले बनाम बंद कर दिया की मौजूदा शेष राशि का ट्रैक रखने की जरूरत है (curb नीचे):

def parens(no, s="", curb=0): 
    # case 1: all open parens used 
    if no == 0: 
     if curb == 0: 
      return [s] 
     return parens(no, s+")", curb-1) 

    # case 2: none are currently open 
    if curb == 0: 
     return parens(no-1, s+"(", curb+1) 

    # case 3: one or more are currently open 
    return parens(no-1, s+"(", curb+1) + parens(no, s+")", curb-1) 

Answer 2

यह memoization का एक स्वाभाविक उपयोग की तरह लगता है। parenthesis(10) में parentheses(6) और parentheses(4) शामिल होंगे, लेकिन parentheses(9)भी शामिल हैं parentheses(6) - इसलिए parenthesis(6) को एक बार गणना की जानी चाहिए। इसके अलावा - सेट का उपयोग करना स्वाभाविक है क्योंकि इससे रोकता है उदा। ()()() दो बार गिनने से, एक बार () +()() और एक बार ()() +() के रूप में।यह निम्नलिखित कोड है, जो या तो n-1 के लिए उत्पन्न कोष्ठकों के आसपास कोष्ठक की एक नई जोड़ी थप्पड़ या पिछले दो कॉल के परिणामों concatenates की ओर जाता है:

cache = {} 

def parentheses(n): 
    if n == 0: 
     return set(['']) 
    elif n in cache: 
     return cache[n] 
    else: 
     par = set('(' + p + ')' for p in parentheses(n-1)) 
     for k in range(1,n): 
      par.update(p+q for p in parentheses(k) for q in parentheses(n-k)) 
     cache[n] = par 
     return par 

उदाहरण के लिए,

>>> for p in parentheses(3): print(p) 

(()()) 
((())) 
()(()) 
()()() 
(())()