🚬 ✋ 🍴 यादृच्छिक कोष्ठक अनुक्रम कैसे उत्पन्न करें 👏🏾 😮 🚵🏻

हेलो, हेब्र!

एल्गोरिदम का परीक्षण करते समय, मेरे पास अक्सर एक यादृच्छिक बाइनरी ट्री जनरेट करने का कार्य होता है। इसके अलावा, विशलिस्ट किसी भी यादृच्छिक पेड़ के लिए कम नहीं है, लेकिन एक समान वितरण से लिया गया है। स्पष्ट सादगी के बावजूद, इस तरह के एक पेड़ को प्रभावी ढंग से बनाने के लिए यह पूरी तरह से निर्विवाद है।

इस लेख के शीर्षक में "ब्रैकेट अनुक्रम" शब्द हैं। इन शब्दों के पीछे, कुछ और छिपा हुआ है, क्योंकि कोष्ठक की मदद से आप बहुत विविध वस्तुओं का वर्णन कर सकते हैं, जिसमें बाइनरी पेड़ भी शामिल हैं। Habré पर एक अलग पोस्ट इस तथ्य के लिए समर्पित था।

इस लेख में, मैं एक यादृच्छिक ब्रैकेट अनुक्रम उत्पन्न करने के कई तरीकों का वर्णन करूंगा, जिसमें रैखिक समय भी शामिल है, और फिर एक अनुक्रम को एक द्विआधारी पेड़ में बदलने का एक उदाहरण देता है। रुचि रखते हैं?

कार्य

N को देखते हुए , लंबाई 2 n के सभी सही अनुक्रमों पर समान वितरण के अनुसार सही ब्रैकेट अनुक्रम उत्पन्न करें।

सूची

यह ज्ञात है कि लंबाई 2 एन के नियमित ब्रैकेट अनुक्रमों की संख्या कैटलन की एनएचटी संख्या के बराबर है

। कैटलन संख्याओं की गणना करने के लिए, स्पष्ट हैं

और पुनरावर्ती

सूत्र।

हमें एक यादृच्छिक संख्या जनरेटर की आवश्यकता है। N को देखते हुए, यह 0 से समान रूप से संभावित यादृच्छिक संख्या उत्पन्न करेगा

। इसके अलावा, सूचियों पर एक यादृच्छिक क्रमपरिवर्तन जनरेटर हमारे लिए उपयोगी है। अजगर में, इसे random.shuffle कहा जाता है। यह हमारे लिए पर्याप्त होगा कि यह रैखिक समय पर काम करता है और क्रम 1,2, ..., n पर समान वितरण के अनुसार एक यादृच्छिक क्रमचय उत्पन्न करता है।

एवोस कहने के तीन तरीके

गतिशील प्रोग्रामिंग की शक्ति

ऐसा विचार है कि सभी सही ब्रैकेट क्रमों को गिना जा सकता है। और, उदाहरण के लिए, यह कैसे करना है, इसका विस्तृत विवरण है। तो, आप इस तरह की योजना को लागू कर सकते हैं।

हम कैटलन की n-वें संख्या पर विचार करते हैं।
हम 1 से एक यादृच्छिक संख्या उत्पन्न करते हैं ।
गतिशील प्रोग्रामिंग और कॉम्बीनेटरियल काउंटिंग का उपयोग करके, हम ब्रैकेट अनुक्रम को उसकी संख्या से पुनर्स्थापित करते हैं।

योजना लगभग उत्कृष्ट है। यानी यदि n छोटा है, तो योजना 30 से कम है, तो यह बहुत अच्छा है। लेकिन यदि n 1'000 के क्रम का है, तो लंबे अंकगणित की आवश्यकता होती है, संदर्भ एल्गोरिदम द्वारा वादा किए गए वर्ग के बजाय क्यूबिक समय काम करेगा, और सामान्य रूप से, गतिशील प्रोग्रामिंग आपके लिए muhra-muhra नहीं है। मुझे लगता है कि मुझे इस तरह की योजना में भी बनाए रखने के लिए बहुत पसीना बहाना पड़ेगा

। आइए वैकल्पिक तरीकों की तलाश करें।

कोशिश करो और जाँच करें

आइए एक बार फिर से कैटलन संख्याओं के स्पष्ट सूत्र पर एक नज़र डालें।

।
वास्तव में, इसका मतलब है कि बहुत सारे सही ब्रैकेट क्रम हैं।

हम एक अनुक्रम को संतुलित कहते हैं यदि इसमें खुलने और बंद होने वाले कोष्ठकों की संख्या समान है। उदाहरण के लिए, अनुक्रम ")(()" , "()()" संतुलित हैं, लेकिन अनुक्रम "()))" नहीं है। जाहिर है, कोई भी सही क्रम संतुलित है। कुल मिलाकर, लंबाई 2n के सभी संभावित संतुलित क्रम मौजूद हैं $\ binom {2n} {n}$ । यदि इनमें से किसी एक क्रम को यादृच्छिक रूप से चुना जाता है, तो यह प्रायिकता के साथ सही होगा

नई योजना।

हम समान वितरण के अनुसार एक यादृच्छिक संतुलित ब्रैकेट अनुक्रम उत्पन्न करते हैं।
शुद्धता के लिए इसकी जाँच करें।
यदि अनुक्रम सही है, तो हम कटौती करते हैं। यदि नहीं, तो चरण 1 पर लौटें।

चलो पहले पैराग्राफ के साथ शुरू करते हैं: इस तरह के एक यादृच्छिक ब्रैकेट अनुक्रम कैसे उत्पन्न करें। चलो एक मनमाना संतुलित क्रम लेते हैं और इसे random.shuffle के माध्यम से मिलाते हैं।

  seq = ['(', ')'] * n random.shuffle(seq)

यदि आप एक कागज और एक कलम के साथ बैठते हैं, तो आप समझ सकते हैं कि किसी भी संतुलित ब्रैकेट अनुक्रम x के लिए वास्तव में मौजूद हैं

क्रमपरिवर्तन जो एक मनमाना प्रारंभिक संतुलित अनुक्रम x में अनुवाद करता है। तो random.shuffle बराबर संभावना के साथ किसी भी संतुलित अनुक्रम उत्पन्न करता है। हम एल्गोरिथ्म प्राप्त करते हैं।

 def tryAndCheck(n): seq = [')', '('] * n while (not correct(seq)): random.shuffle(seq) return seq

यह समय का मूल्यांकन करने के लिए रहता है। सही और random.shuffle रूटीन प्रति पंक्ति काम करते हैं। मुख्य लूप के कितने पुनरावृत्तियों होंगे? हम जानते हैं कि सही ब्रैकेट अनुक्रम संभाव्यता के साथ उत्पन्न होता है

। तब हम कह सकते हैं कि हमारे पास एक सिक्का है जिसमें ईगल संभावना के साथ गिरता है

। चटाई की गणना करना आवश्यक है। चील की संख्या की प्रतीक्षा करना जब तक कि चील गिर न जाए।

एक विकल्प के रूप में, आप चटाई को पेंट कर सकते हैं। सूत्र द्वारा प्रतीक्षा करें और इस तरह से कुछ प्राप्त करें:

या प्रसिद्ध तथ्यों का लाभ उठाएं। एक तरह से या दूसरे, चटाई। संपूर्ण एल्गोरिथ्म के लिए प्रतीक्षा समय है

।

कोशिश करो और ठीक करो

ठीक है, लेकिन क्या होगा अगर हमें वास्तव में एक बड़ा अनुक्रम चाहिए? प्रति मिलियन वर्ण अनुक्रम।

रैखिक एल्गोरिथ्म अब इतना तुच्छ नहीं है। 1992 में माइक एटकिंसन और जॉर्जेस सैक द्वारा एक अलग लेख उन्हें समर्पित किया गया था। मैं यहां अपनी दृष्टि प्रस्तुत करूंगा कि लेख में क्या लिखा गया है।

हमें मैजिक फंक्शन की जरूरत है। इनपुट पर, फ़ंक्शन को एक संतुलित ब्रैकेट अनुक्रम लेना चाहिए, और आउटपुट पर, समान लंबाई का सही एक लौटाएं। यह सुनिश्चित करना महत्वपूर्ण है कि फ़ंक्शन समान रूप से अनुक्रम को स्कैटर करता है, अर्थात् प्रत्येक नियमित अनुक्रम y के लिए बिल्कुल n + 1 संतुलित अनुक्रम x है , जैसे कि f (x) = y । यदि फ़ंक्शन को रैखिक समय के लिए गणना की जा सकती है, तो बिंदु टोपी में है।

हम समान वितरण और वापसी f (x) के अनुसार एक संतुलित संतुलित अनुक्रम x उत्पन्न करते हैं।

समारोह में सभी चाल। यदि आप चाहते हैं, तो आप रोक सकते हैं और खुद के साथ आने की कोशिश कर सकते हैं। यह काम नहीं करता है, यह ठीक है अब मैं सिलेंडर से गणित के सिलेंडर से एक खरगोश निकालूंगा, और सभी लोग ठीक हो जाएंगे।

मान लीजिए कि हमारे पास एक काउंटर है, और शुरू में यह शून्य है। सीक्वेंस पर चलते हैं। प्रत्येक खोलने वाले ब्रैकेट के लिए हम एक बिंदु जोड़ेंगे, प्रत्येक समापन ब्रैकेट के लिए - घटाना।

 balance = 0 for c in seq: balance += 1 if c == '(' else -1

नीचे दिया गया ग्राफ़ दिखाता है कि जैसे-जैसे आप अनुक्रम के साथ आगे बढ़ते हैं, balance काउंटर बदलता है।

अलग-अलग रंगों में चित्रित दृश्यों को इनडोमोकोलॉजिकल कहा जाता है। यानी सामान्य तौर पर, एक अनुक्रम अनिर्णायक होता है, यदि उस पर काउंटर केवल प्रारंभ और अंत बिंदु पर शून्य मान लेता है। आप देख सकते हैं कि इनडोमोकोलॉजिकल अनुक्रम दो श्रेणियों में आते हैं: वे जो पूरी तरह से शून्य स्तर से ऊपर हैं, और नीचे वाले। पूर्व को सकारात्मक अनुक्रम कहा जाएगा, बाद का नकारात्मक।

हम नकारात्मक बाद की कुल लंबाई की गणना करते हैं और इसे आधे में विभाजित करते हैं। प्राप्त मूल्य को अनुक्रम दोष कहा जाता है। सही दृश्यों में शून्य दोष है। यदि लंबाई 2 n के सही क्रम में सभी कोष्ठक प्रतिलोम द्वारा प्रतिस्थापित किए जाते हैं , तो दोष n होगा।

सावधान, खरगोश! चांग-फेलर प्रमेय। दोष कश्मीर के साथ लंबाई 2 एन के ब्रैकेट अनुक्रमों की संख्या कैटलन की एनएचटी संख्या के बराबर है C_n

और k पर निर्भर नहीं करता है।

प्रमेय दिलचस्प है कि यह लंबाई 2 n के सभी संतुलित अनुक्रमों को समान आकार के n + 1 वर्गों में विभाजित करता है, और कक्षाओं के बीच एक अलग वर्ग होता है जिसमें सभी सही ब्रैकेट अनुक्रम होते हैं। इसलिए, हम एक ऐसे फंक्शन के साथ आने की कोशिश कर सकते हैं, जो प्रत्येक अनुक्रम x को दोष k के साथ सही अनुक्रम y के साथ एन्कोड करता है, और इस मामले में, हम विशिष्ट रूप से x को अनुक्रम y और दोष k से फिर से जोड़ सकते हैं ।

यदि हम इस तरह के फ़ंक्शन के साथ आने का प्रबंधन करते हैं, तो हमें यह पता चलता है कि प्रत्येक सही अनुक्रम के लिए 0 से n तक दोषों के साथ बिल्कुल n + 1 संतुलित हैं। यह आसान लग रहा है।

प्रयास 1।

आइए सभी नकारात्मक बाद और उल्टे को लें, अर्थात कोष्ठक को विपरीत से बदलें।
$\ texttt {({{color {red}) ((() () ({color {red})} (}) \ rightarrow \ texttt {() {\ color {green} ())} (() )) {\ रंग {हरा} ()}$
इसके अलावा इस तरह के एक समारोह, यह सभी अनिर्णायक दृश्यों की स्थिति को बरकरार रखता है। माइनस - हम सभी जानकारी खो देते हैं जिसके बारे में बाद की स्थिति नकारात्मक थी और जो सकारात्मक थी। यह जानते हुए भी कि दोष 3 था, हम उदाहरण से प्रारंभिक अनुक्रम को पुनर्स्थापित नहीं कर सकते।

प्रयास २।

आइए सभी नकारात्मक बाद में पलटें और फिर उन्हें अंत तक रखें।
$\ texttt {({{color {red})} (} (() () ({color {red})} (}) \ rightarrow \ texttt {() ()) {\ color {green} () )} {\ color {हरा} ()}$
अब, दोष को जानकर, हम नकारात्मक परिणामों को ठीक कर सकते हैं। लेकिन हमने वह स्थान खो दिया जहां वे थे।

प्रयास ३।

हम एक मनमाना अनिर्णायक ऋणात्मक क्रम लेते हैं और इसके चरम कोष्ठक को फाड़ देते हैं, और परिणाम को उल्टा कर देते हैं।
$\ texttt {) {\ color {red}) () (} (} \ rightarrow \ texttt {\ color {हरा} ())}$
इस तरह के ऑपरेशन को चालाक उलटा कहा जाता है और जी द्वारा निरूपित किया जाता है। चूंकि अनुक्रम अनिर्णायक और नकारात्मक है, परिणाम हमेशा सही ब्रैकेट अनुक्रम होगा। फ़ंक्शन जी की चाल यह है कि, एक तरफ, यह प्रतिवर्ती है, और दूसरे पर, हमारे पास दो अतिरिक्त ब्रैकेट हैं, जिनका उपयोग नकारात्मक परिणाम की स्थिति को एनकोड करने के लिए किया जा सकता है।

हम प्रयास 2 समाप्त करते हैं, केवल अब हम रिवर्स क्रम में नकारात्मक अनुक्रमों को बाहर निकालते हैं और जी समारोह के माध्यम से उन्हें उल्टा करते हैं:
$\ textut {({{color {red})} (} (() () ({color {red})} (}) \ rightarrow \ texttt {() {\ color {blue} \ bf [} () ) {\ रंग {नीला} \ bf [} {\ रंग {नीला} \ bf]} {\ रंग {हरा} ई}}} _ {\ texttt {\ रंग {लाल}} (}) \ {texttt {{रंग {नीला} \ bf]} {\ color {हरा} ()}} _ \ texttt {\ color {लाल})} (})$
जैसा कि आप उदाहरण से देख सकते हैं, नकारात्मक बाद की स्थिति को मुक्त कोष्ठक द्वारा नोट किया जा सकता है। मैंने उन्हें नीले रंग में उजागर किया और उन्हें चौकोर बना दिया। अक्षर ई का अर्थ है खाली क्रम।

पता करें कि कौन से कोष्ठक हरे हैं और कौन से नीले रंग के दोषपूर्ण हो सकते हैं, जिसका अर्थ है कि आप स्वयं प्रारंभिक अनुक्रम को पुनर्स्थापित कर सकते हैं। यह वही है जो आपको चाहिए!

एटकिन्सन और सैक ने समारोह के लिए एक पुनरावर्ती सूत्र का प्रस्ताव रखा:

यहां $\ अल्फा$ अनिर्णायक परवर्ती, और

- शेष।

नीचे मैं विस्तारित पुनरावृत्ति के साथ पायथन में एल्गोरिथ्म के कार्यान्वयन को संलग्न कर रहा हूं। यह समझना आसान है कि एल्गोरिथ्म रैखिक समय चलाता है।

 def tryAndFix(n): seq = ['(', ')'] * n random.shuffle(seq) stack = [] result = [] balance = 0 prev = 0 for pos in range( len(seq) ): balance += 1 if seq[pos] == '(' else -1 if balance == 0: if seq[prev] == '(': result.extend( seq[ prev : pos + 1 ] ) else: result.append('(') stack.append( [ ')' if v == '(' else '(' for v in seq[ prev + 1 : pos ] ] ) prev = pos + 1 for lst in reversed(stack): result.append(')') result.extend(lst) return result

पेड़ की पीढ़ी

अगर आप इस जगह तक पढ़ते हैं, तो मैं बहुत खुश हूं। वह सब कुछ अनुक्रम को एक पेड़ में बदलना है।

लंबाई 2 की ब्रैकेट अनुक्रम n + 1 कोने के साथ मनमाने ढंग से समतल के पेड़ों को पूरी तरह से घेरते हैं। वास्तव में, गहराई से खोज चलाएँ। शीर्ष पर प्रवेश द्वार पर, हम निकास ब्रैकेट लिखते हैं, बाहर निकलने पर - समापन ब्रैकेट।

इसी समय, एन + 1 से मनमानी मेष के पेड़ों को एक-से-एक पत्राचार में अपने बाइनरी से बाइनरी पेड़ों के साथ लगाया जा सकता है। जरूरत है कि सबसे पहले "बाएं बच्चे - दाएं पड़ोसी" के रूप में मनमानी मेहराब के पेड़ों को लिखना है, और फिर सही पड़ोसी को सही बच्चे का नाम देना है।

हमारे साथ बने रहने के लिए धन्यवाद!

संदर्भ

"यूनिफ़ॉर्म रैंडम जनरेशन ऑफ़ बैलेंस्ड पेरेंटेसिस स्ट्रिंग्स" डीबी अर्नोल्ड, एमआर स्लीप, 1980 - रैंडम ब्रैकेट सीक्वेंस की पीढ़ी पर पहला लेख।
"यादृच्छिक पर द्विआधारी पेड़ पैदा करना" एमडी एटकिंसन, जे- आर। बोरी, 1992
पास्टबिन पर स्क्रिप्ट

यादृच्छिक कोष्ठक अनुक्रम कैसे उत्पन्न करें