algorithm - किसी दिए गए शब्द के लिए एनाग्राम ढूंढना




data-structures language-agnostic (8)

उदाहरण एल्गोरिदम:

Open dictionary
Create empty hashmap H
For each word in dictionary:
  Create a key that is the word's letters sorted alphabetically (and forced to one case)
  Add the word to the list of words accessed by the hash key in H

किसी दिए गए शब्द के सभी आरेखों की जांच करने के लिए:

Create a key that is the letters of the word, sorted (and forced to one case)
Look up that key in H
You now have a list of all anagrams

निर्माण करने के लिए अपेक्षाकृत तेज़, लुकअप पर तेजस्वी तेज।

दो शब्द एनाग्राम हैं यदि उनमें से एक के पास एक और शब्द के समान अक्षर हैं।

उदाहरण: Anagram और Nagaram एनाग्राम (केस-असंवेदनशील) हैं।

अब इस तरह के कई सवाल हैं। यह पता लगाने के लिए कुछ दृष्टिकोण हैं कि दो तार आरेख हैं या नहीं:

1) तारों को Sort और उनकी तुलना करें।

2) इन तारों के लिए frequency map बनाएं और जांचें कि वे समान हैं या नहीं।

लेकिन इस मामले में, हमें एक शब्द दिया जाता है (सादगी के लिए हम केवल एक शब्द मानते हैं और इसमें केवल एक शब्द एनाग्राम होगा) और हमें इसके लिए एनाग्राम ढूंढना होगा।

समाधान जो मेरे मन में है वह यह है कि, हम शब्द के लिए सभी क्रमपरिवर्तन उत्पन्न कर सकते हैं और यह जांच सकते हैं कि इनमें से कौन सा शब्द शब्दकोश में मौजूद है । लेकिन स्पष्ट रूप से, यह बेहद अक्षम है। हां, शब्दकोश भी उपलब्ध है।

तो हमारे यहां क्या विकल्प हैं?

मैंने एक समान थ्रेड में भी पढ़ा है कि Tries का उपयोग करके कुछ किया जा सकता है लेकिन व्यक्ति ने एल्गोरिदम के बारे में समझाया नहीं था और हमने पहले स्थान पर ट्री का उपयोग क्यों किया था, केवल एक क्रियान्वयन भी पाइथन या रूबी में प्रदान किया गया था। तो यह वास्तव में सहायक नहीं था इसलिए मैंने इस नए धागे को बनाया है। अगर कोई अपना कार्यान्वयन साझा करना चाहता है (सी, सी ++ या जावा के अलावा) तो कृपया इसे भी समझाएं।


एक समाधान है - नक्शा प्राइम संख्या वर्णमाला वर्णों के लिए और प्रमुख संख्या गुणा करें

For ex - 

    a -> 2
    b -> 3
    ......
    .......
    ......
    z -> 101

इसलिए

'ab' -> 6
'ba' -> 6
'bab' -> 18
'abba' -> 36
'baba' -> 36

दिए गए शब्द के लिए MUL_number प्राप्त करें। शब्दकोश से सभी शब्द वापस करें जिनके पास दिए गए शब्द के समान MUL_number है


मैं अनुमान लगाता हूं कि एक नए समाधान के साथ आया था। यह अंकगणितीय के मौलिक प्रमेय का उपयोग करता है। तो विचार पहली 26 प्राइम संख्याओं की एक सरणी का उपयोग करना है। फिर इनपुट शब्द में प्रत्येक अक्षर के लिए हमें संबंधित प्राइम नंबर ए = 2, बी = 3, सी = 5, डी = 7 ... और फिर हम अपने इनपुट शब्द के उत्पाद की गणना करते हैं। इसके बाद हम शब्दकोश में प्रत्येक शब्द के लिए ऐसा करते हैं और यदि कोई शब्द हमारे इनपुट शब्द से मेल खाता है, तो हम इसे परिणामी सूची में जोड़ते हैं। सभी एनाग्रामों का एक ही हस्ताक्षर होगा क्योंकि

1 से अधिक कोई भी पूर्णांक या तो एक प्रमुख संख्या है, या इसे प्राइम संख्याओं (ऑर्डर को अनदेखा कर) के अद्वितीय उत्पाद के रूप में लिखा जा सकता है।

कोड यहाँ है। मैं शब्द को अपरकेस में परिवर्तित करता हूं और 65 ए की स्थिति है जो मेरे पहले प्राइम नंबर से मेल खाती है:

private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
        37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
        107, 109, 113 };

यह विधि है:

 private long calculateProduct(char[] letters) {
    long result = 1L;
    for (char c : letters) {
        if (c < 65) {
            return -1;
        }
        int pos = c - 65;
        result *= PRIMES[pos];
    }
    return result;
}

यह इस बात पर निर्भर करता है कि आप अपना शब्दकोश कैसे संग्रहीत करते हैं। यदि यह शब्दों की एक सरल सरणी है, तो कोई एल्गोरिदम रैखिक से तेज नहीं होगा।

अगर इसे हल किया गया है, तो यहां एक दृष्टिकोण है जो काम कर सकता है। मैंने अभी इसका आविष्कार किया है, लेकिन मुझे लगता है कि यह रैखिक दृष्टिकोण से तेज़ है।

  1. अपने शब्दकोश को डी के रूप में बताएं, वर्तमान उपसर्ग एस एस = 0 के रूप में;
  2. आप अपने शब्द के लिए आवृत्ति मानचित्र बनाते हैं। चलिए इसे एफ द्वारा दर्शाते हैं।
  3. शब्दकोश में प्रत्येक अक्षर को शुरू करने के लिए बाइनरी खोज पॉइंटर्स का उपयोग करना। चलिए पी द्वारा पॉइंटर्स के इस सरणी को इंगित करते हैं।
  4. ए से ज़ेड के प्रत्येक चार सी के लिए, यदि एफ [सी] == 0, इसे छोड़ दें, अन्यथा
    • एस + = सी;
    • एफ [सी] -;
    • पी <- प्रत्येक चरित्र के लिए मैं पी [i] = एस + i के साथ शुरू होने वाले पहले शब्द के सूचक।
    • जब तक आपको अपने शब्द के लिए कोई मिलान नहीं मिल जाता है या जब तक आप पाते हैं कि ऐसा कोई मिलान मौजूद नहीं है, तब तक चरण 4 पर कॉल करें।

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


सभी क्रमपरिवर्तन उत्पन्न करना आसान है, मुझे लगता है कि आप चिंतित हैं कि शब्दकोश में उनके अस्तित्व की जांच करना "अत्यधिक अक्षम" हिस्सा है। लेकिन यह वास्तव में इस बात पर निर्भर करता है कि आप शब्दकोश के लिए किस डेटा संरचना का उपयोग करते हैं: बेशक, आपके उपयोग के मामले में शब्दों की एक सूची अक्षम होगी। कोशिशों की बात करते हुए, वे शायद एक आदर्श प्रतिनिधित्व होगा, और काफी कुशल भी होंगे।

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


हम जानते हैं कि यदि दो शब्दों में समान लंबाई नहीं है, तो वे एनाग्राम नहीं हैं। तो आप एक ही लंबाई के शब्दों के समूहों में अपने शब्दकोश को विभाजित कर सकते हैं।

अब हम इन समूहों में से केवल एक पर ध्यान केंद्रित करते हैं और मूल रूप से सभी शब्दों में इस छोटे ब्रह्मांड में बिल्कुल वही लंबाई होती है।

यदि प्रत्येक अक्षर स्थिति एक आयाम है, और उस आयाम में मान पत्र पर आधारित है (ASCII कोड कहें)। फिर आप शब्द वेक्टर की लंबाई की गणना कर सकते हैं।

उदाहरण के लिए, 'ए' = 65, 'बी' = 66, फिर length("AB") = sqrt(65*65 + 66*66) कहें। जाहिर है, length("AB") = length("BA")

जाहिर है, यदि दो शब्द एनाग्राम हैं, तो उनके वैक्टरों की लंबाई समान है। अगला सवाल यह है कि, यदि दो शब्द (अक्षरों की एक ही संख्या) वैक्टरों की लंबाई समान है, तो क्या वे एनाग्राम हैं? सहजता से, मैं नहीं कहूंगा, क्योंकि उस लंबाई के साथ सभी वैक्टर एक क्षेत्र बनाते हैं, कई हैं। निश्चित नहीं है, क्योंकि हम इस मामले में पूर्णांक स्थान में हैं, वास्तव में कितने हैं।

लेकिन कम से कम यह आपको अपने शब्दकोश को और भी विभाजित करने की अनुमति देता है। अपने शब्दकोश में प्रत्येक शब्द के लिए, वेक्टर की दूरी की गणना करें: के for(each letter c) { distance += c*c }; distance = sqrt(distance); for(each letter c) { distance += c*c }; distance = sqrt(distance);

फिर लंबाई n सभी शब्दों के लिए एक नक्शा बनाएं, और दूरी के साथ इसे कुंजी करें और मान लंबाई n के शब्दों की एक सूची है जो उस विशेष दूरी को उत्पन्न करती है।

आप प्रत्येक दूरी के लिए एक नक्शा बनायेंगे।

फिर आपका लुकअप निम्नलिखित एल्गोरिदम बन जाता है:

  1. शब्द की लंबाई के आधार पर सही शब्दकोश मानचित्र का प्रयोग करें
  2. अपने शब्द के वेक्टर की लंबाई की गणना करें
  3. उस लंबाई से मेल खाने वाले शब्दों की सूची देखें
  4. सूची के माध्यम से जाएं और एक बेवकूफ एल्गोरिदम का उपयोग करके एनाग्राम चुनें अब उम्मीदवारों की सूची बहुत कम हो गई है

static void Main(string[] args)
{

    string str1 = "Tom Marvolo Riddle";
    string str2 = "I am Lord Voldemort";

    str2=  str2.Replace(" ", string.Empty);
    str1 = str1.Replace(" ", string.Empty);
    if (str1.Length != str2.Length)
        Console.WriteLine("Strings are not anagram");
    else
    {
        str1 = str1.ToUpper();
        str2 = str2.ToUpper();
        int countStr1 = 0;
        int countStr2 = 0;
        for (int i = 0; i < str1.Length; i++)
        {
            countStr1 += str1[i];
            countStr2 += str2[i];

        }
        if(countStr2!=countStr1)
            Console.WriteLine("Strings are not anagram");
        else Console.WriteLine("Strings are  anagram");

    }
    Console.Read();
}

  • शब्दकोश में प्रत्येक शब्द के लिए आवृत्ति गणना वेक्टर की गणना करें, वर्णमाला सूची की लंबाई का एक वेक्टर।
  • वर्णमाला सूची की लंबाई के एक यादृच्छिक Gaussian वेक्टर उत्पन्न करें
  • प्रत्येक यादृच्छिक शब्द की गिनती वेक्टर को इस यादृच्छिक दिशा में प्रोजेक्ट करें और मान स्टोर करें (मान डालें कि मानों की सरणी क्रमबद्ध है)।

  • एक नए परीक्षण शब्द को देखते हुए, इसे शब्दकोष शब्दों के लिए उपयोग की जाने वाली एक ही यादृच्छिक दिशा में प्रोजेक्ट करें।

  • समान मूल्य पर मानचित्र वाले शब्दों की सूची ढूंढने के लिए बाइनरी खोज करें।
  • सत्यापित करें कि उपरोक्त के रूप में प्राप्त प्रत्येक शब्द वास्तव में एक वास्तविक एनाग्राम है। यदि नहीं, तो सूची से इसे हटा दें।
  • सूची के शेष तत्वों को वापस करें।

पीएस: उपर्युक्त प्रक्रिया प्राइम नंबर प्रक्रिया का एक सामान्यीकरण है जो संभावित रूप से बड़ी संख्या में हो सकती है (और इसलिए कम्प्यूटेशनल परिशुद्धता के मुद्दों)





anagram