संख्या सरणी

Question

एक स्ट्रिंग 12345 और a =1, b =2 की तरह नंबर मानचित्रण के लिए एक वर्णमाला को देखते हुए से संभव वर्णमाला स्ट्रिंग्स की संख्या का पता लगाएं .., y=25, z=26; दी गई स्ट्रिंग से संभावित वर्णमाला तारों की संख्या को खोजने के लिए एक कोड लिखें।

ई.एक्स. स्ट्रिंग 12345 में मैपिंग {12-3-4-5, 1-23-4-5, 1-2-3-4-5} से {lcde,awde, abcde} के रूप में संभव वर्णमाला तार हैं।

मेरे पास यह कैसे करना है इसका एक सामान्य विचार है। मुझे लगता है कि यह रिकर्सिव होगा। पहले अंक को देखें और इसके परिणामस्वरूप चार मैपिंग जोड़ें और फिर उप सरणी (1, आकार -1) के साथ पुन: साझा करें। दो पहले अंक भी देखें और देखें कि वे < = 26 हैं। यदि ऐसा है, तो परिणाम और रिकर्स (2, आकार -2) में जोड़ें। ऐसा तब तक करें जब तक कि संख्या सरणी खाली न हो।

हालांकि मैं वास्तविक कार्यान्वयन पर अटक गया हूं। क्या रिकर्सन से ऐसा करने का कोई शानदार तरीका है?

Answer 1

यह वर्ड ब्रेक समस्या के समान है। आप इसे हल करने के लिए एक ही दृष्टिकोण का उपयोग कर सकते हैं। आप समग्र चलने वाले समय को कम करने के लिए ज्ञापन का उपयोग कर सकते हैं। यदि आप अपने दिए गए उदाहरण में देखते हैं:

12-3-4-5, 1-23-4-5, 1-2-3-4-5 

4 और 5 दोहराया जा रहा है और आप इसे बार-बार गणना कर रहे हैं। आप पहली बार गणना की गई इंडेक्स के क्रमपरिवर्तन को संग्रहीत कर सकते हैं और जब भी आप उसी इंडेक्स पर जाते हैं तो इसका उपयोग कर सकते हैं।

छद्म कोड:

recursive_function(string,index) 
if you have already calculated values for this index in previous call 
    return value 

recursive_function(string,index+1) 
if possible 
    recursive_function(string,index+2) 

store this value for future use. 

विवरण:

आप कहते सूचकांक i के लिए पुनरावर्ती कॉल प्राप्त होने पर, जब आप इस कॉल (मूल रूप से वर्तमान प्रत्यावर्तन से लौट रहे) के साथ किया जाता है आप पहले से ही इस्तेमाल/गणना/सभी संभावित मूल्यों को मिला (सूचकांक i पर शुरू होने वाली उप-स्ट्रिंग के लिए सभी क्रमपरिवर्तन)। आप इन मानों को स्टोर कर सकते हैं क्योंकि यदि आप देखेंगे कि कई बार इंडेक्स i पर कुछ अन्य इंडेक्स से j (j<i) कहेंगे। तो अब इस समय आप के रूप में आप पहले से ही सूचकांक i के लिए मान की गणना की है और कहा कि j

Answer 2

का एक ही ध्यान दिए बिना हो जाएगा बस इस कोडिंग खत्म यह अपने आप में जगह के बजाय सूचकांक i के लिए और अधिक पुनरावर्ती कॉल से लौट सकते हैं, विचार @dream_machine से है

असल में, यह एक बैक ट्रैकिंग एल्गोरिथ्म है, जटिलता हे (2n!) है, left ट्रैकिंग पता करने के लिए उत्पादन के लिए स्ट्रिंग रखना चाहिए रखने की आवश्यकता है।

लगता है कि एल्गोरिदम बहुत धीमा है, शायद इसे गति देने के लिए कुछ ज्ञापन जोड़ने की आवश्यकता है।

void helper(int start, string &s, string &path, vector<string> &result, int); 

vector<string> 
getPossibleCombo(string &s) { 
    vector<string> result; 
    string path; 
    helper(0, s, path, result, s.size()); 
    return result; 
} 

void helper(int start, string &s, string &path, vector<string> &result, int left) { 
    if (start == s.size() && left == 0) { 
     result.push_back(path); 
     return; 
    } 

    for (int i = start; i < s.size(); i++) { 
     path.push_back('a' + (s[i] - '0') - 1); 
     helper(i + 1, s, path, result, left - 1); 
     path.pop_back(); 

     if (i < s.size() - 1 && s[i] > '0' && s[i] <= '2') { // can try two. 
      if (s[i] == '2' && s[i+1] > '6') 
       continue; 
      int c = (s[i] - '0') * 10 + s[i + 1] - '0'; 
      path.push_back('a' + c - 1); 
      helper(i + 2, s, path, result, left - 2); 
      path.pop_back(); 
     } 
    } 
} 

int main() { 
    string s("12345"); 
    auto r = getPossibleCombo(s); 
    for (auto &s : r) { 
     cout << s << endl; 
    } 
} 

उत्पादन

bash-3.2$ g++ -std=c++11 -g test2.cpp && ./a.out 
abcde 
awde 
lcde