خوارزمية للعثور على الكلمات المكتوبة برقم

Question

أحاول إيجاد طريقة لتحديد جميع الكلمات الممكنة التي يمكن تهجئتها برقم معين، مع تعيين الحروف الهجائية للقيم.

أريد في النهاية العثور على حل مناسب لأي تعيين قيمة مكون من رقم واحد أو رقمين لحرف ما، ولكن للتوضيح، افترض أن A=1، B=2،...ض = 26.

مثال: 12322 يمكن أن يكون مساويا ل abcbb (1,2,3,2,2), lcbb (12,3,2,2), awbb (1,23,2,2), abcv (1,2,3,22), awv (1,23,22), ، أو lcv (12,3,22).

---

إليك ما فكرت به حتى الآن:

سأبني شجرة من كل الكلمات الممكنة باستخدام الرقم.

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

سأقوم بعد ذلك بتحليل الرقم رقمًا تلو الآخر بدءًا من الرقم الأقل أهمية.

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

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

للتوضيح، ل 12322 سوف تبدو شجرتي مثل هذا:

                *
             /     \
            /       \
           2         22
         /         /   \
        2         3     23
      /   \      / \    /
    3      23   2   12 1
   / \    /    /
  2   12 1    1
 /
1 

للحصول على الكلمات، سأجتاز كل المسارات الممكنة من الأوراق إلى العقد.

---

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

Answer 1

وافترض أن لديك aleady كل تركيبة ممكنة من [2, 3, 2, 2]، ما من شأنه أن تكون مزيجا من [1, 2, 3, 2, 2] (إضافة [1] في الرأس)؟ ليس من الصعب أن نستنتج أنه يجب أن تكون:

  A1: put [1] to the head of all_the_combinations_of[1,2,3,2,2] and 
  A2: put [1*10 + 2] to the head of all_the_combinations_of[2,3,2,2] if [1*10 + 2 <=26]

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

def comb a
    c = []
    puts a.inspect
    return [a] if a.length <= 1

    c =  comb(a[1..-1]).map {|e| [a[0]] + e}
    if a[0] * 10 + a[1] <= 26
            c += comb(a[2..-1]).map { |f| [a[0] * 10 + a[1]] + f }
    end
    c
end

h = Hash[*(1..26).to_a.zip(('A'..'Z').to_a).flatten]
#h.keys.sort.each {|k| puts "#{k}=>#{h[k]}"}

comb([1,2,3,2,2]).each do |comb|
    puts comb.map {|k| h[k]}.join
end

[1, 2, 3, 2, 2]
  A1 [2, 3, 2, 2]
      [3, 2, 2]
         [2, 2]
            [2]
             []
      [2, 2]
         [2]
          []
  A2 [3, 2, 2]
      [2, 2]
         [2]
          []
ABCBB
ABCV
AWBB
AWV
LCBB
LCV

Answer 2

لا تحتاج فعليًا إلى إنشاء شجرة - فقط كرر:

1. خذ رقما واحدا.لنرى إن كان بإمكاننا تكوين كلمة باعتبار أنها حرف في ذاتها، والتكرار.
2. عندما نعود من التكرار، حاول إضافة رقم آخر (إذا كنا 1 أو 2 سابقًا)، ثم التكرار.

Answer 3

وحل القوة الغاشمة، سيكون لملء حيوي مجموعة من 1 إلى N، حيث يحتوي على عنصر a[i] مجموعة من السلاسل التي تشكل a[1]a[2]a[3]...a[i] بعد التوسع. يمكنك ملء [1] من stratch، ثم ملء a[2]، استنادا إلى مجموعة a[1] والحرف الثاني في السلسلة. ثم لك ملء [3]، وما إلى ذلك وفي كل STED أنك لا تملك إلا أن ننظر إلى الوراء لa[i-1] وa[i-2] (وs[i-1] وs[i]، حيث s هو رقم التسلسل الخاص بك).

وأخيرا، وبعد أن تملأ a[n]، فإنه سوف تحتوي على الجواب.

لالمثال "12322"، وتسلسل يصبح:

a[1] = { "a" }
a[2] = { a + 'b' | a in a[1] } union { "l" } = { "ab", "l" }
a[3] = { a + 'c' | a in a[2] } union { a + 'w' | a in a[1] } = { "abc", "lc", "aw" }
a[4] = { a + 'b' | a in a[3] } union { } = { "abcb", "lcb", "awb" }
a[5] = { a + 'b' | a in a[4] } union { a + 'v' | a in a[3] } = { "abcbb", "lcbb", "awbb", "abcv", "lcv", "awv" }

وهذا هو الأساس النسخة البرمجة الديناميكية من الحل عودي أعلاه.

Answer 4

هناك طريقة بديلة للقيام بذلك وهي عكس المشكلة:

• بالنظر إلى قاموس الكلمات، قم بحساب السلاسل الرقمية التي سيتم إنشاؤها، وقم بتخزين هذه البيانات في بنية الخريطة/القاموس، أي.الجدول ['85'] = 'مرحبًا'
• بالنسبة لكل رقم من أرقام x الأولى من الرقم الذي تبحث عنه، تحقق مما إذا كان موجودًا في الجدول، على سبيل المثال.الجدول. يحتوي على المفتاح ('1')، الجدول. يحتوي على المفتاح ('12')، ...
• إذا كنت تحاول العثور على تسلسلات الكلمات، فقم بإنشاء الكلمات التي تبدأ في كل موقع في السلسلة الرقمية، ثم قم بإجراء بحث متكرر للعثور على جميع العبارات من ذلك.