लाल और नीली गेंदों की एक स्ट्रिंग को देखते हुए, रंगों को एक साथ जोड़ने के लिए स्वैप की न्यूनतम संख्या

Question

हमें फ़ॉर्म की एक स्ट्रिंग दी गई है: आरबीबीआर, जहां आर - लाल और बी - नीला।

हमें रंगों को एक साथ जोड़ने के लिए आवश्यक न्यूनतम स्वैप ढूंढने की आवश्यकता है। उपर्युक्त मामले में आरआरबीबी या बीबीआरआर प्राप्त करने के लिए उत्तर 1 होगा।

मुझे लगता है कि आंशिक रूप से सॉर्ट किए गए सरणी को सॉर्ट करने के लिए एल्गोरिदम की तरह यह उपयोगी होगा क्योंकि एक साधारण प्रकार हमें स्वैप की संख्या देगा, लेकिन हम minimum स्वैप की संख्या चाहते हैं।

कोई विचार?

यह कथित तौर पर this के अनुसार एक माइक्रोसॉफ्ट साक्षात्कार प्रश्न है।

Answer 1

स्ट्रिंग पर एक पास ले जाएं और लाल रंग की संख्या (# आर) और ब्लूज़ की संख्या (# बी) की गणना करें। फिर पहली # आर गेंदों (# आर) में लाल रंग की संख्या और पहली # बी गेंदों (# बी) में नीली गेंदों की संख्या को गिनने वाला दूसरा पास लें। जितना कम (# आर - # आर) और (# बी - # बी) आवश्यक स्वैप की न्यूनतम संख्या होगी।

Answer 2

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

Answer 3

हमें स्ट्रिंग एस दिया जाता है जिसे हमें अंतिम स्ट्रिंग एफ = आर^ए बी^बी या बी^बी आर^ए में परिवर्तित करना है। एस और एफ के बीच मतभेदों की संख्या भी होनी चाहिए क्योंकि प्रत्येक गलत जगह के लिए पूरक पूरक बी होगा। तो एस और दोनों संभावित एफ के बीच मतभेदों की न्यूनतम संख्या क्यों न पाएं और 2 से विभाजित करें?

उदाहरण के लिए, आप एस = RBRRBRBR जो में बदलने चाहिए RRRRRBBB दिया जाता है
या BBBRRRRR

प्रत्येक संभावना के लिए हर किरदार के लिए एस और एफ के बीच मतभेद की तुलना में, वहाँ प्रत्येक संभव के लिए 4 मतभेद हैं अंतिम स्ट्रिंग इतनी परवाह किए बिना न्यूनतम 2 स्वैप है।

Answer 4

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

Answer 5

मुझे लगता है कि स्वैप की संख्या वेक्टर को सॉर्ट करने के लिए आवश्यक परिवर्तनों की संख्या से ली जा सकती है। This क्रमपरिवर्तन वेक्टर के साथ ऐसा करने का उदाहरण है।

Answer 6

यह तकनीकी जवाब नहीं है, लेकिन मैंने इसे और अधिक सहजता से देखा।

आरआरबीबीबीबीआर को आरबीआर में कम किया जा सकता है, क्योंकि आर के समूह को एक ब्लॉक के रूप में स्थानांतरित किया जा सकता है। इसका मतलब है कि सरणी वास्तव में सिर्फ आरबी के एन सेट है।

एकमात्र चीज जो आरबी ब्लॉक के एन सेटों की संख्या है (अंतिम के लिए अपूर्ण ब्लॉक सहित)।

• RBR -> 1 स्वैप आरआरबी के लिए (आरबी ब्लॉक के 2 सेट, आरबी और आर) (2 आरबी ब्लॉकों का पूरा सेट) प्राप्त करने के लिए
• RBRB-> 1 स्वैप RRBB को पाने के लिए
• RBRBRB -> 2 स्वैप RRRBBB को पाने के लिए (3 आरबी ब्लॉकों का पूरा सेट)
• RBRBRBRB -> आरबी = 3 स्वैप के 4 सेट

तो यह सामान्यीकरण करने के लिए, स्वैप की संख्या की जरूरत = एन आरबी के सेट ब्लॉक (अपूर्ण ब्लॉक सहित) और घटाना 1.