algorithm - एंग्राम शब्द समूह के लिए एल्गोरिथ्म




anagram data-processing (9)

अक्षरों के लिए एक अद्वितीय प्रधान संख्या असाइन करें az

अपने शब्द सरणी को दोहराएं, प्रत्येक शब्द में अक्षरों के आधार पर प्राथमिकताएं उत्पाद बनाएं।
इसी शब्द के साथ, उस शब्द को अपनी शब्द सूची में स्टोर करें

सरणी को क्रमबद्ध करें, उत्पाद द्वारा आरोही।

प्रत्येक उत्पाद परिवर्तन पर एक नियंत्रण ब्रेक करने के लिए, सरणी को दोहराएं।

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

इनपुट:

man car kile arc none like

उत्पादन:

man
car arc
kile like
none

सबसे अच्छा उपाय जो मैं अब विकसित कर रहा हूं वह हैशटेबल पर आधारित है, लेकिन मैं समीकरण के बारे में सोच रहा हूं कि एंग्राम शब्द को पूर्णांक मान में कनवर्ट करें।

उदाहरण: आदमी => 'मी' + 'ए' + 'एन' लेकिन यह अनूठे मूल्य नहीं देगा।

कोई उपाय?

सी # में निम्नलिखित कोड देखें:

string line = Console.ReadLine();
string []words=line.Split(' ');
int[] numbers = GetUniqueInts(words);
for (int i = 0; i < words.Length; i++)
{
    if (table.ContainsKey(numbers[i]))
    {
        table[numbers[i]] = table[numbers[i]].Append(words[i]);
    }
    else
    {
        table.Add(numbers[i],new StringBuilder(words[i]));
    }

}

समस्या यह है कि GetUniqueInts(string []) विधि को कैसे विकसित किया GetUniqueInts(string [])


आपको बड़े पूर्णांक (या वास्तव में एक बिट वेक्टर) की आवश्यकता होगी, लेकिन निम्नलिखित कार्य हो सकता है

प्रत्येक पत्र की पहली घटना उस पत्र के लिए बिट संख्या को सौंपी जाती है, दूसरी घटना उस पत्र + 26 के लिए बिट संख्या प्राप्त करती है

उदाहरण के लिए

एक # 1 = 1 बी # 1 = 2 सी # 1 = 4 ए # 2 = 2 ^ 26 बी # 2 = 2 ^ 27

इसके बाद आप इन पत्रों के आधार पर शब्द के लिए एक अनन्य मूल्य प्राप्त करने के लिए इन दोनों को एक साथ योग कर सकते हैं।

शब्द मानों के लिए आपकी संग्रहण आवश्यकताओं को निम्न होगा:

n * 26 बिट्स

जहां n किसी भी दोहराए गए अक्षर की संख्या की अधिकतम संख्या है।


गिगल्स के लिए एक पायथन संस्करण:

from collections import defaultdict
res = defaultdict(list)
L = "car, acr, bat, tab, get, cat".split(", ")

for w in L:
    res["".join(sorted(w))].append(w)

print(res.values())

मुझे नहीं लगता कि आपको कस्टम हैश फ़ंक्शन के साथ एक हैश तालिका से बेहतर कुछ भी मिलेगा (जो उस शब्द को पत्र लिखने से पहले होता है)।

पत्रों का योग कभी काम नहीं करेगा, क्योंकि आप वास्तव में 'एसी' और 'बीबी' अलग नहीं कर सकते।


मैंने गोडेल प्रेरित योजना का इस्तेमाल किया:

पत्रों के लिए P_1 को P_1 के लिए निहित करें (किसी भी क्रम में, लेकिन छोटे अक्षरों को छोटे प्रिम्स देने के लिए सबसे छोटे हश मूल्य प्राप्त करने के लिए)

शब्द में अक्षरों के हिस्टोग्राम का निर्माण किया।

इसके बाद हैश मान प्रत्येक अक्षर के संबंधित प्राइवेट का उत्पाद है जो इसकी आवृत्ति की शक्ति को उठाया गया है। यह प्रत्येक एनाग्राम के लिए एक अनन्य मान देता है।

पायथन कोड:

primes = [2, 41, 37, 47, 3, 67, 71, 23, 5, 101, 61, 17, 19, 13, 31, 43, 97, 29, 11, 7, 73, 83, 79, 89, 59, 53]


def get_frequency_map(word):
    map = {}

    for letter in word:
        map[letter] = map.get(letter, 0) + 1

    return map


def hash(word):
    map = get_frequency_map(word)
    product = 1
    for letter in map.iterkeys():
        product = product * primes[ord(letter)-97] ** map.get(letter, 0)
    return product

यह चतुराई से बड़ी संख्या में फैक्टरिंग की समस्या (भी मुश्किल के रूप में जाना जाता है) में उपनग्राम खोजने की मुश्किल समस्या को बदल देती है ...


सी में, मैंने सिर्फ निम्नलिखित हैश को लागू किया है, जो मूल रूप से एक 26-बिट बिटमैस्क पर है कि क्या शब्दकोश में शब्द में एक विशेष अक्षर है या नहीं। इसलिए, सभी आलेखों में एक ही हैश है। हैश बार-बार अक्षरों को ध्यान में नहीं रखता, इसलिए कुछ अतिरिक्त ओवरलोडिंग हो जाएगा, लेकिन यह अभी भी मेरे पर्ल कार्यान्वयन से भी तेज होने का प्रबंधन करता है।

#define BUCKETS 49999

struct bucket {
    char *word;
    struct bucket *next;
};

static struct bucket hash_table[BUCKETS];

static unsigned int hash_word(char *word)
{
    char *p = word;
    unsigned int hash = 0;

    while (*p) {
        if (*p < 97 || *p > 122) {
            return 0;
        }
        hash |= 2 << (*p - 97);
        *p++;
    }

    return hash % BUCKETS;
}

ओवरलोड की गई बाल्टियाँ और लिंक की गई सूची आदि के रूप में जोड़ दी गई। फिर सिर्फ एक फ़ंक्शन लिखो जो सुनिश्चित करता है कि हैश मान से मेल खाने वाले शब्द समान लंबाई हैं और प्रत्येक में से अक्षर 1 से 1 हैं और एक मैच के रूप में वापस आते हैं।


मैं हैशिंग का उपयोग नहीं करेगा क्योंकि यह देखने के लिए अतिरिक्त जटिलता जोड़ता है और जोड़ता है। हैशिंग, सॉर्टिंग और गुणाएं सभी यूनिक्स को ट्रैक करने के साथ सरल सरणी-आधारित हिस्टोग्राम समाधान से धीमी गति से होने वाली हैं। सबसे खराब मामला ओ (2 एन) है:

// structured for clarity
static bool isAnagram(String s1, String s2)
{
    int[] histogram = new int[256];

    int uniques = 0;

    // scan first string
    foreach (int c in s1)
    {
        // count occurrence
        int count = ++histogram[c];

        // count uniques
        if (count == 1)
        {
            ++uniques;
        }
    }

    // scan second string
    foreach (int c in s2)
    {
        // reverse count occurrence
        int count = --histogram[c];

        // reverse count uniques
        if (count == 0)
        {
            --uniques;
        }
        else if (count < 0) // trivial reject of longer strings or more occurrences
        {
            return false;
        }
    }

    // final histogram unique count should be 0
    return (uniques == 0);
}

अनाग्राम निम्नलिखित तरीके से पा सकते हैं:

  1. शब्द की लंबाई मैच होना चाहिए।
  2. पूर्णांक मान के संदर्भ में प्रत्येक चरित्र के अतिरिक्त कार्य करें। यह राशि मैच की जाएगी यदि आप समान रूप से anagram पर करते हैं।
  3. पूर्णांक मान के मामले में प्रत्येक चरित्र का गुणन करना। यदि आप अनाग्राम पर समान कार्य करते हैं तो मूल्यांकन मूल्य का मिलान होगा।

इसलिए मैंने ऊपर तीन मान्यताओं के माध्यम से सोचा, हम अनग्राम पा सकते हैं। यदि मैं गलत हूं तो मुझे सही करों।

उदाहरण: एबीसी सीबीए

दोनों शब्दों की लंबाई 3 है

दोनों शब्दों के लिए व्यक्तिगत वर्णों का योग 294 है।

दोनों शब्दों के लिए व्यक्तिगत वर्णों का प्रोडक्ट 941094 है


बस अन्य उपयोगी उत्तरों के अलावा सरल अजगर समाधान भी जोड़ना चाहते हैं:

def check_permutation_group(word_list):
    result = {}

    for word in word_list:
        hash_arr_for_word = [0] * 128  # assuming standard ascii

        for char in word:
            char_int = ord(char)
            hash_arr_for_word[char_int] += 1

        hash_for_word = ''.join(str(item) for item in hash_arr_for_word)

        if not result.get(hash_for_word, None):
            result[str(hash_for_word)] = [word]
        else:
            result[str(hash_for_word)] += [word]

return list(result.values())




data-processing