मान लीजिए वहाँ दिया जाता है दो स्ट्रिंग:स्ट्रिंग स्थानांतरण एल्गोरिथ्म
String s1= "MARTHA"
String s2= "MARHTA"
।
मानते हैं कि दूरी की गणना केवल स्वैप होती है, यहां क्रमिक क्रम पर चलने वाला एक विचार है, जो रैखिक समय में चलता है।
एल्गोरिदम का पहला चरण यह सुनिश्चित कर रहा है कि दो तार वास्तव में उनके चरित्र सामग्री में बराबर हैं। यह एक हैश तालिका (या एक निश्चित सरणी जो सभी वर्णमाला को कवर करता है) का उपयोग कर रैखिक समय में किया जा सकता है। यदि वे नहीं हैं, तो एस 2 को एस 1 का क्रमपरिवर्तन नहीं माना जा सकता है, और "स्वैप गिनती" अप्रासंगिक है।
दूसरा चरण एस 2 से एस 1 को बदलने के लिए आवश्यक न्यूनतम स्वैप की गणना करता है। यह क्रमपरिवर्तन पी का निरीक्षण करके किया जा सकता है जो एस 1 से एस 2 में परिवर्तन के अनुरूप है। उदाहरण के लिए, यदि s1 = "abcde" और s2 = "badce", तो p = (2,1,4,3,5), जिसका अर्थ है कि स्थिति 1 में तत्व # 2 है, स्थिति 2 में तत्व # 1, आदि शामिल है। क्रमिक समय में क्रमपरिवर्तन permutation cycles में तोड़ दिया जा सकता है। उदाहरण में चक्र (2,1) (4,3) और (5) हैं। न्यूनतम स्वैप गणना प्रति चक्र आवश्यक स्वैप की कुल गणना है। लम्बाई के चक्र को "इसे ठीक करने" के लिए के-1 स्वैप की आवश्यकता होती है। इसलिए, स्वैप की संख्या एन-सी है, जहां एन स्ट्रिंग लम्बाई है और सी चक्रों की संख्या है। हमारे उदाहरण में, परिणाम 2 है (स्वैप 1,2 और फिर 3,4)।
अब, वहाँ दो समस्याओं यहाँ हैं, और मुझे लगता है कि मैं भी उन्हें अभी हल करने के लिए थक गया हूँ :)
1) मेरे समाधान मानती है कि कोई चरित्र दोहराया है, जो हमेशा मामला नहीं है। स्वैप गिनती की गणना करने के लिए कुछ समायोजन की आवश्यकता है।
2) मेरा फॉर्मूला # मिनस्वाप्स = एन-सी को सबूत चाहिए ... मुझे इसे वेब में नहीं मिला।
कई edit distance एल्गोरिदम हैं, दिए गए विकीपेडा लिंक में कुछ लिंक हैं।
उनमें से कोई भी केवल ध्यान में नहीं आता है। – IVlad
आपकी समस्या इतनी आसान नहीं है, क्योंकि स्वैप को गिनने से पहले आपको यह सुनिश्चित करने की आवश्यकता है कि प्रत्येक स्वैप इन दो तारों के बीच "दूरी" (समानता में) को कम कर दे। फिर वास्तव में आप गिनती की तलाश करते हैं लेकिन आपको सबसे छोटी गिनती (या कम से कम मुझे लगता है) की तलाश करनी चाहिए, अन्यथा एक और प्राप्त करने के लिए स्ट्रिंग को स्वैप करने के अनंत तरीके मौजूद हैं।
आपको सबसे पहले जांच करनी चाहिए कि कौन से charaters पहले से ही मौजूद हैं, फिर प्रत्येक चरित्र के लिए यह नहीं दिखता है कि कोई जोड़ा है जिसे स्विंग किया जा सकता है ताकि तारों के बीच की अगली दूरी कम हो। फिर जब तक आप प्रक्रिया खत्म नहीं कर लेते हैं तब तक पुन: प्रयास करें।
यदि आप इसे प्रभावी ढंग से नहीं करना चाहते हैं, लेकिन केवल स्वैप की संख्या को गिनती करें, जिसमें प्रत्येक अच्छी तरह से रखे गए चरित्र और 0 अन्यथा 1 है। जब आप हर बिट 1 है तो आप समाप्त कर देंगे।
और यह स्वैप की न्यूनतम संख्या को कैसे सुनिश्चित करता है? यदि आप केवल अंधेरे से तत्वों को स्वैप करते हैं, या कम से कम एक मृत अंत में स्ट्रिंग को परिवर्तित नहीं करते हैं तो आप अनंत लूप में समाप्त हो सकते हैं। – IVlad
पुनरावृत्ति बाधा तारों के बीच की दूरी को कम करना है। यदि आप सुनिश्चित करते हैं कि प्रत्येक चरण दूरी कम कर देता है तो आप अनंत लूप में कैसे समाप्त हो सकते हैं?यह अटक गया है कि यह सुनिश्चित कर रहा है कि दो तार "बराबर स्वैप" नहीं हैं लेकिन यह गारंटी देता है कि कुछ भी किए बिना लूप न करें। दृष्टिकोण को _greedy_ कहा जाता है जो यह सुनिश्चित करता है कि, यदि स्थानीय इष्टतम रखा जाता है (प्रत्येक पुनरावृत्ति दूरी को कम करके), तो वैश्विक इष्टतम प्रत्यक्ष परिणाम होता है। – Jack
तब मुझे लगता है कि हम दो वस्तुओं 'i' और' j' के स्वैप के बारे में बात कर रहे हैं जहां 'i = j + 1' या उपाध्यक्ष जैसी कोई बाधा नहीं है। इसके अलावा क्योंकि ओपी ने आसन्न स्वैप नहीं कहा था, लेकिन बस स्वैप .. – Jack
होमवर्क टैग, हो सकता है? – KevenK
ओह वाह, 110 प्रश्न, 3 उत्तर, और केवल 6 अपवॉट्स? – KevenK