वर्ड जंबल एल्गोरिदम

Question

एक शब्द jumble (i.e. ofbaor) दिया गया है, वास्तविक शब्द बनाने के लिए अक्षरों को अनसुलझा करने का दृष्टिकोण क्या होगा (यानी foobar)? मैं इसे कुछ दृष्टिकोण देख सकता था, और मुझे लगता है कि मुझे पता है कि मैं इसे .NET में कैसे करूँगा, लेकिन मैं यह देखने के लिए उत्सुक हूं कि कुछ अन्य समाधान किस तरह दिखते हैं (हमेशा यह देखने में खुशी होती है कि मेरा समाधान इष्टतम है या नहीं)।

यह होमवर्क या ऐसा कुछ भी नहीं है, मैंने पेपर के स्थानीय कॉमिक्स अनुभाग (हां, अच्छा ओल 'फैशन न्यूजप्रिंट) में एक शब्द झटका देखा, और मेरे अंदर इंजीनियर ने सोचना शुरू कर दिया।

संपादित करें: कृपया कुछ छद्म कोड या वास्तविक कोड पोस्ट करें यदि आप कर सकते हैं; इस तरह के उदाहरण देखकर भाषा ज्ञान का प्रयास करना और विस्तार करना हमेशा अच्छा होता है।

Answer 1

एक शब्दकोश है जो सॉर्ट किए गए क्रम में प्रत्येक शब्द के अक्षरों से कुंजी है। फिर आपको अक्षरों को एक तरह से झुकाएं - उस क्रमबद्ध-अक्षर स्ट्रिंग द्वारा शब्दकोश में सभी शब्दों को देखें।

तो, एक उदाहरण है, शब्द 'भालू' और 'नंगे' के रूप में शब्दकोश में होगा इस प्रकार है:

key word 
----- ------ 
aber bear 
aber bare 

और तुम गड़बड़ी, 'earb' दिया जाता है, तो आप चाहते अक्षरों को 'aber' में सॉर्ट करें और शब्दकोश में दोनों संभावित शब्दों को देखने में सक्षम हो।

Answer 2

स्ट्रिंग के सभी क्रमपरिवर्तन बनाएं, और उन्हें एक शब्दकोश में देखें।

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

Answer 3

कोडप्रोजेक्ट में कुछ लेख here और here हैं। दूसरा रिकर्सन का उपयोग करता है। विकिपीडिया में कुछ एल्गोरिदम here की रूपरेखा भी शामिल है। विकिपीडिया लेख में जंबो नामक एक कार्यक्रम का भी उल्लेख है जो एक अधिक मानवीय दृष्टिकोण का उपयोग करता है जो मानव की तरह समस्या को हल करता है। समस्या के कुछ दृष्टिकोण होने लगते हैं।

Answer 4

स्ट्रिंग की लंबाई के आधार पर व्हर्लविंड का दृष्टिकोण तेजी से हो सकता है, लेकिन ऐसा करने का एक वैकल्पिक तरीका है जिसमें कम या कम ओ (एन) जटिलता स्ट्रिंग के सभी क्रमपरिवर्तन बनाने और उन्हें देखने के बजाय है, आप शब्दकोश में सभी शब्दों के माध्यम से जाएं और देखें कि प्रत्येक इनपुट स्ट्रिंग से बनाया जा सकता है या नहीं।

एक वास्तव में स्मार्ट एल्गोरिथ्म है कि पहले से शब्दकोश में शब्दों की संख्या जानता है कुछ इस तरह कर सकता है:

sort letters in jumbled string 
if factorial(length of jumbled string) > count of words in dictionary: 
    for each word in dictionary: 
     sort letters in dictionary word 
     if sorted letters in dictionary word == sorted letters in jumbled string: 
      append original dictionary word to acceptable word list 
else: 
    create permutation list of jumbled letters 
    for each permutation of letters: 
     search in dictionary for permutation 
     if permutation in dictionary: 
      add word to acceptable word list 

Answer 5

http://www.codeproject.com/KB/game/Anagrams2.aspx