algorithm - تعريف - العثور على الجناس الناقص لكلمة معينة



بحث عن الجناس في البلاغة (8)

كلمتين هي الجناس الناقصة إذا كان أحدهما يحتوي على نفس الأحرف تمامًا مثل كلمة أخرى.

مثال: Anagram & Nagaram هي من الجناس Nagaram (غير حساسة لحالة الأحرف).

الآن هناك العديد من الأسئلة المشابهة لهذا. هناك طريقتان لمعرفة ما إذا كانت السلاسل النجمية هي:

1) Sort السلاسل ومقارنتها.

2) إنشاء frequency map لهذه السلاسل والتحقق مما إذا كانت هي نفسها أم لا.

ولكن في هذه الحالة ، يتم إعطاؤنا بكلمة (من أجل البساطة ، دعونا نفترض كلمة واحدة فقط ، وسوف يكون لها جناج مفرد الكلمة فقط) ، ونحن بحاجة إلى إيجاد الجناس الناقص لذلك.

الحل الذي يدور في ذهني هو أنه يمكننا توليد كل التباديل للكلمة والتحقق من أي من هذه الكلمات موجودة في القاموس . لكن من الواضح أن هذا غير فعال إلى حد كبير. نعم ، القاموس متاح أيضا.

إذن ما هي البدائل المتوفرة لدينا هنا؟

قرأت أيضًا في سلسلة مشابهة أن شيئًا ما يمكن إجراؤه باستخدام Tries لكن الشخص لم يشرح ما هي الخوارزمية ولماذا استخدمنا Trie في المقام الأول ، تم تقديم تطبيق فقط في Python أو Ruby. لذلك لم يكن مفيدًا حقًا ، ولهذا السبب قمت بإنشاء هذا الموضوع الجديد. إذا أراد أحد الأشخاص مشاركة تطبيقه (بخلاف C أو C ++ أو Java) ، فيرجى توضيح ذلك أيضًا.

https://src-bin.com


Answer #1

تحقق أولاً إذا كان طول السلاسل متماثلاً. ثم تحقق مما إذا كان مجموع الأحرف في كل من السلاسل متماثلة (أي مجموع رمز ascii) ثم الكلمات هي anagrams آخر لا الجناس الناقص


Answer #2

توصلت إلى حل جديد أعتقد. ويستخدم نظرية الأساسي للحساب. لذا فإن الفكرة هي استخدام مجموعة من أول 26 عددًا أساسيًا. ثم لكل حرف في كلمة الإدخال نحصل على العدد الأولي المقابل A = 2 ، B = 3 ، C = 5 ، D = 7 ... وبعد ذلك نحسب منتج كلمة الإدخال الخاصة بنا. بعد ذلك نقوم بذلك لكل كلمة في القاموس وإذا كانت الكلمة تتطابق مع كلمة الإدخال الخاصة بنا ، فسنقوم بإضافتها إلى القائمة الناتجة. كل الجناس الناقصة لها نفس التوقيع

أي عدد صحيح أكبر من 1 هو إما رقم أولي ، أو يمكن كتابته كمنتج فريد للأعداد الأولية (تجاهل الترتيب).

ها هي الكود أقوم بتحويل الكلمة إلى UPPERCASE و 65 هو موضع A الذي يتوافق مع أول رقم أولي:

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;
}

Answer #3

حاول تنفيذ حل hashmap

public class Dictionary {

    public static void main(String[] args){

    String[] Dictionary=new String[]{"dog","god","tool","loot","rose","sore"};

    HashMap<String,String> h=new HashMap<String, String>();

    QuickSort q=new QuickSort();

    for(int i=0;i<Dictionary.length;i++){

        String temp =new String();

        temp= q.quickSort(Dictionary[i]);//sorted word e.g dgo for dog

        if(!h.containsKey(temp)){
           h.put(temp,Dictionary[i]);
        }

        else
        {
           String s=h.get(temp);
           h.put(temp,s + " , "+ Dictionary[i]);
        }
    }

    String word=new String(){"tolo"};

    String sortedword = q.quickSort(word);

    if(h.containsKey(sortedword.toLowerCase())){ //used lowercase to make the words case sensitive

        System.out.println("anagrams from Dictionary   :  " + h.get(sortedword.toLowerCase()));
    }

}

Answer #4

حل واحد هو - تعيين الأرقام الأولية لأحرف الأبجدية وعدد أولي مضاعفة

For ex - 

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

وبالتالي

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

احصل على MUL_number للكلمة الممنوحة. عودة جميع الكلمات من القاموس التي لها نفس MUL_number ككلمة معينة


Answer #5

نحن نعلم أنه إذا لم يكن لكلمتين نفس الطول ، فهما لا ينطبعان. حتى تتمكن من تقسيم القاموس الخاص بك في مجموعات من الكلمات من نفس الطول.

نحن نركز الآن على واحدة فقط من هذه المجموعات وأساسا كل الكلمات لها نفس الطول في هذا الكون الأصغر.

إذا كان موضع كل حرف بعدًا ، وكانت القيمة في هذا البعد تستند إلى الحرف (على سبيل المثال ، رمز ASCII). ثم يمكنك حساب طول كلمة متجه.

على سبيل المثال ، قل "A" = 65 ، "B" = 66 ، ثم length("AB") = sqrt(65*65 + 66*66) . من الواضح أن length("AB") = length("BA") .

من الواضح أنه إذا كانت الكلمتان هي الجناس الناقصة ، فإن متجهاتها لها نفس الطول. السؤال التالي ، إذا كان لكلمتين (من نفس العدد من الأحرف) المتجهات نفس الطول ، فهل هما ناعقتان؟ حدسي ، أود أن أقول لا ، بما أن جميع المتجهات ذات الطول تشكل كرة ، فهناك الكثير. لست متأكدًا ، نظرًا لأننا نوجد في المساحة الصحيحة في هذه الحالة ، فكم عددها في الواقع.

ولكن على الأقل يسمح لك بتقسيم القاموس الخاص بك إلى أبعد من ذلك. لكل كلمة في القاموس الخاص بك ، قم بحساب مسافة vector: 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. تذهب من خلال القائمة واختيار الجناس الناقص باستخدام خوارزمية ساذجة هو الآن يتم تخفيض قائمة المرشحين إلى حد كبير

Answer #6

هذا يعتمد على كيفية تخزين القاموس الخاص بك. إذا كانت مجموعة بسيطة من الكلمات ، فلن تكون الخوارزمية أسرع من الخطية.

إذا تم فرزها ، فإليك طريقة قد تعمل. لقد اخترعت ذلك الآن ، لكني أعتقد أنه أسرع من النهج الخطي.

  1. دلالة القاموس الخاص بك كما D ، البادئة الحالية باسم S. S = 0 ؛
  2. يمكنك إنشاء خريطة تردد لكلمتك. دعنا نرمز إليه بـ F.
  3. استخدام البحث عن البحث عن المؤشرات الثنائية لبدء كل حرف في القاموس. دعونا تدل على هذه المجموعة من المؤشرات ب.
  4. لكل حرف c من A إلى Z ، إذا كانت F [c] == 0 ، فتخطها ، وإلا
    • S + = c؛
    • F [c] -؛
    • P <- لكل حرف i P [i] = مؤشر إلى أول كلمة تبدأ بـ S + i.
    • استدعاء الخطوة الرابعة بشكل متكرر حتى تجد تطابقًا لكلمتك أو حتى تجد أنه لا يوجد مثل هذا التطابق.

هذه هي الطريقة التي سأفعل بها ، على أي حال. يجب أن يكون هناك نهج أكثر تقليدية ، ولكن هذا أسرع ثم خطي.


Answer #7
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();
}

Answer #8
  • حساب متجه عدد التردد لكل كلمة في القاموس ، متجه طول طول قائمة الأبجدية.
  • توليد ناقل غوسي عشوائي لطول قائمة الأبجدية
  • مشروع كل متجه عدد الكلمات القاموس في هذا الاتجاه العشوائي وتخزين القيمة (إدراج مثل أن يتم فرز مجموعة من القيم).

  • إذا أعطيت كلمة اختبار جديدة ، فاعرضها في نفس الاتجاه العشوائي المستخدم لكلمات القاموس.

  • قم بإجراء بحث ثنائي للعثور على قائمة الكلمات التي تعين لنفس القيمة.
  • تحقق من أن كل كلمة تم الحصول عليها على النحو الوارد أعلاه هي في الواقع جناس حقيقي. إذا لم يكن كذلك ، فقم بإزالته من القائمة.
  • إرجاع العناصر المتبقية من القائمة.

ملاحظة: الإجراء أعلاه هو تعميم الإجراء الأول من الرقم الذي قد يؤدي إلى أعداد كبيرة (وبالتالي قضايا الدقة الحسابية)





anagram