مشكلة الخوارزمية:مجموعات الحروف

Question

أحاول كتابة جزء من التعليمات البرمجية الذي سيقوم بما يلي:

خذ الأرقام من 0 إلى 9 وقم بتعيين حرف واحد أو أكثر لهذا الرقم.على سبيل المثال:

0 = N,
1 = L,
2 = T,
3 = D,
4 = R,
5 = V or F,
6 = B or P,
7 = Z,
8 = H or CH or J,
9 = G

عندما يكون لدي رمز مثل 0123، يكون من السهل تشفيره.من الواضح أنه سيشكل الرمز NLTD.عندما يتم تقديم رقم مثل 5،6 أو 8، تختلف الأمور.رقم مثل 051 قد يؤدي إلى أكثر من احتمال:

الدوري الوطني لكرة القدم الأمريكية واتحاد كرة القدم الأميركي

يجب أن يكون واضحًا أن الأمر يصبح "أسوأ" مع الأرقام الأطول التي تتضمن عدة أرقام مثل 5،6 أو 8.

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

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

تحديث:

المزيد من الخلفية:(وشكرًا جزيلا على الردود السريعة!)

الفكرة وراء سؤالي هي بناء برنامج نصي يساعد الأشخاص على تحويل الأرقام التي يريدون تذكرها بسهولة إلى كلمات يسهل تذكرها.يشار إلى هذا أحيانًا باسم "علم الأعداد الزائفة".

أريد أن يمنحني البرنامج النصي جميع المجموعات الممكنة التي يتم الاحتفاظ بها بعد ذلك مقابل قاعدة بيانات من الكلمات المجردة.هذه الكلمات المجردة تأتي للتو من القاموس وتم حذف جميع الأحرف التي ذكرتها في سؤالي منها.بهذه الطريقة، يمكن عادةً بسهولة ربط الرقم المراد ترميزه بسجل واحد أو أكثر من سجلات قاعدة البيانات.وعندما يحدث ذلك، سينتهي بك الأمر بقائمة من الكلمات التي يمكنك استخدامها لتذكر الرقم الذي تريد تذكره.

Answer 1

البنية العامة التي تريد الاحتفاظ برقمك -> تعيينات الحروف هي مصفوفة أو مصفوفات، تشبه:

// 0 = N, 1 = L, 2 = T, 3 = D, 4 = R, 5 = V or F, 6 = B or P, 7 = Z, 
// 8 = H or CH or J, 9 = G
$numberMap = new Array (
    0 => new Array("N"),
    1 => new Array("L"),
    2 => new Array("T"),
    3 => new Array("D"),
    4 => new Array("R"),
    5 => new Array("V", "F"),
    6 => new Array("B", "P"),
    7 => new Array("Z"),
    8 => new Array("H", "CH", "J"),
    9 => new Array("G"),
);

بعد ذلك، القليل من المنطق العودي يمنحنا وظيفة مشابهة لما يلي:

function GetEncoding($number) {
    $ret = new Array();
    for ($i = 0; $i < strlen($number); $i++) {
        // We're just translating here, nothing special.
        // $var + 0 is a cheap way of forcing a variable to be numeric
        $ret[] = $numberMap[$number[$i]+0];
    }
}

function PrintEncoding($enc, $string = "") {
    // If we're at the end of the line, then print!
    if (count($enc) === 0) {
        print $string."\n";
        return;
    }

    // Otherwise, soldier on through the possible values.
    // Grab the next 'letter' and cycle through the possibilities for it.
    foreach ($enc[0] as $letter) {
        // And call this function again with it!
        PrintEncoding(array_slice($enc, 1), $string.$letter);
    }
}

ثلاثة هتافات للعودية!سيتم استخدام هذا عبر:

PrintEncoding(GetEncoding("052384"));

وإذا كنت تريدها حقًا كمصفوفة، فالعب باستخدام التخزين المؤقت للإخراج ثم انفجر باستخدام " " كسلسلة مقسمة.

Answer 2

ويمكن القيام بذلك بسهولة بشكل متكرر.

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

Answer 3

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

0 = N,
1 = L,
2 = T,
3 = D,
4 = R,
5 = V or F,
6 = B or P,
7 = Z,
8 = H or CH or J,
9 = G

التعيين العكسي الخاص بك هو:

N = 0,
L = 1,
T = 2,
D = 3,
R = 4,
V = 5,
F = 5,
B = 6,
P = 6,
Z = 7,
H = 8,
J = 8,
G = 9

لاحظ أنه لا يوجد تعيين لـ "ch"، لأنه سيتم إسقاط "c"، وسيتم تحويل "h" إلى 8 على أي حال.

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

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

Answer 4

عادة ما يتم حل هذا النوع من المشاكل عن طريق التكرار.في روبي، سيكون هناك حل واحد (سريع وقذر).

@values = Hash.new([])


@values["0"] = ["N"] 
@values["1"] = ["L"] 
@values["2"] = ["T"] 
@values["3"] = ["D"] 
@values["4"] = ["R"] 
@values["5"] = ["V","F"] 
@values["6"] = ["B","P"] 
@values["7"] = ["Z"] 
@values["8"] = ["H","CH","J"] 
@values["9"] = ["G"]

def find_valid_combinations(buffer,number)
 first_char = number.shift
 @values[first_char].each do |key|
  if(number.length == 0) then
     puts buffer + key
  else
     find_valid_combinations(buffer + key,number.dup)
    end
 end
end

find_valid_combinations("",ARGV[0].split(""))

وإذا قمت بتشغيل هذا من سطر الأوامر فسوف تحصل على:

$ ruby r.rb 051
NVL
NFL

هذا مرتبط ب بحث القوة الغاشمة و التراجع

Answer 5

هنا حل عودي في بايثون.

#!/usr/bin/env/python

import sys

ENCODING = {'0':['N'],
            '1':['L'],
            '2':['T'],
            '3':['D'],
            '4':['R'],
            '5':['V', 'F'],
            '6':['B', 'P'],
            '7':['Z'],
            '8':['H', 'CH', 'J'],
            '9':['G']
            }

def decode(str):
   if len(str) == 0:
       return ''
   elif len(str) == 1:
       return ENCODING[str]
   else:
       result = []
       for prefix in ENCODING[str[0]]:
           result.extend([prefix + suffix for suffix in decode(str[1:])])
       return result

if __name__ == '__main__':
   print decode(sys.argv[1])

مثال الإخراج:

$ ./demo 1
['L']
$ ./demo 051
['NVL', 'NFL']
$ ./demo 0518
['NVLH', 'NVLCH', 'NVLJ', 'NFLH', 'NFLCH', 'NFLJ']

Answer 6

هل يمكنك القيام بما يلي:إنشاء مصفوفة النتائج.قم بإنشاء عنصر في المصفوفة بقيمة ""

قم بمراجعة الأرقام، على سبيل المثال 051 لتحليل كل واحد على حدة.

في كل مرة يتم العثور على تطابق 1 إلى 1 بين رقم، قم بإضافة القيمة الصحيحة إلى كافة العناصر الموجودة في مصفوفة النتائج.لذلك "" يصبح N.

في كل مرة يتم العثور على تطابق من 1 إلى كثير، أضف صفوفًا جديدة إلى مصفوفة النتائج باستخدام خيار واحد، وقم بتحديث النتائج الحالية باستخدام الخيار الآخر.لذا فإن N تصبح NV ويتم إنشاء عنصر جديد NF

ثم الرقم الأخير هو تطابق 1 إلى 1 ، لذا فإن العناصر الموجودة في صفيف النتائج تصبح NVL و NFL

لإنتاج حلقة النتائج من خلال مصفوفة النتائج أو طباعتها أو أي شيء آخر.

Answer 7

يترك pن تكون قائمة بجميع مجموعات الأحرف الممكنة لسلسلة أرقام معينة s حتى nذ رقم.

ثم سيتم إنشاء الخوارزمية التالية pن+1:

digit = s[n+1];
foreach(letter l that digit maps to)
{
    foreach(entry e in p(n))
    {
        newEntry = append l to e;
        add newEntry to p(n+1);
    }
}

التكرار الأول هو إلى حد ما حالة خاصة، منذ ص_-1 غير محدد.يمكنك ببساطة تهيئة p₀ كقائمة بجميع الأحرف الممكنة للحرف الأول.

لذا، مثال 051 الخاص بك:

التكرار 0:

p(0) = {N}

التكرار 1:

digit = 5
foreach({V, F})
{
    foreach(p(0) = {N})
    {
        newEntry = N + V  or  N + F
        p(1) = {NV, NF}
    }
}

التكرار 2:

digit = 1
foreach({L})
{
    foreach(p(1) = {NV, NF})
    {
        newEntry = NV + L  or  NF + L
        p(2) = {NVL, NFL}
    }
}

Answer 8

ربما يكون النموذج الذي تريده شيئًا مثل:

function combinations( $str ){
$l = len( $str );
$results = array( );
if ($l == 0) { return $results; }
if ($l == 1)
{  
   foreach( $codes[ $str[0] ] as $code )
   {
    $results[] = $code;
   }
   return $results;
}
$cur = $str[0];
$combs = combinations( substr( $str, 1, $l ) );
foreach ($codes[ $cur ] as $code)
{
    foreach ($combs as $comb)
    {
        $results[] = $code.$comb;
    }
}
return $results;}

هذا أمر قبيح، pidgin-php لذا يرجى التحقق منه أولاً.الفكرة الأساسية هي إنشاء كل مجموعة من السلسلة من [1..n] ثم إضافة كل رمز ممكن لـ str[0] إلى مقدمة كل هذه المجموعات.ضع في اعتبارك أنه في أسوأ الحالات سيكون لهذا أداء متسارع في طول السلسلة، لأن هذا القدر الكبير من الغموض موجود بالفعل في نظام الترميز الخاص بك.

Answer 9

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