Các ký tự của các chữ cái và số trong một số điện thoại

Question

Đối với lớp khoa học máy tính của chúng tôi, chúng ta cần viết một chương trình (bằng C++) lấy đầu vào ký tự và xuất các hoán vị có thể của nó theo bàn phím số trên điện thoại, để lại các ký tự không phải chữ số tại chỗ.

Ví dụ, nhập 2 đầu ra 2, A, B, C. Nhập 23 kết quả đầu ra 23, A3, B3, C3, 2D, 2E, 2F, AD, AE, AF, BD, BE, BF, v.v.

Ứng dụng được cung cấp cho chương trình này là tìm các hoán vị của số điện thoại "vanity" cho một số điện thoại cụ thể.

Hiện nay, chương trình tôi đã viết không thậm chí biên dịch, và tôi sợ thuật toán Tôi đang sử dụng là không đúng:

#include <iostream> 
#include <multimap.h> 
#include <vector> 
using namespace std; 

// Prototypes 
void initLetterMap(multimap<char,char> &lmap); 
void showPermutations(const vector<string> &perms); 
vector<string> getPermutations(const string &phoneNumber,const multimap<char,char> &lmap); 
vector<char> getLetters(char digit, const multimap<char,char> &lmap); 


// Declarations 
void initLetterMap(multimap<char,char> &lmap) { 
    lmap.insert(pair<char,char>('1','1')); 
    lmap.insert(pair<char,char>('2','2')); 
    lmap.insert(pair<char,char>('2','A')); 
    lmap.insert(pair<char,char>('2','B')); 
    lmap.insert(pair<char,char>('2','C')); 
    lmap.insert(pair<char,char>('3','3')); 
    lmap.insert(pair<char,char>('3','D')); 
    lmap.insert(pair<char,char>('3','E')); 
    lmap.insert(pair<char,char>('3','F')); 
    // ... 
} 

vector<char> getLetters(char digit, const multimap<char,char> &lmap) { 
    multimap<char,char>::iterator it; 
    pair<multimap<char,char>::iterator,multimap<char,char>::iterator> range; 
    vector<char> result; 

    if (isdigit(digit)) { 
     range = lmap.equal_range(digit); 
     for (it=range.first;it!=range.second;++it) { 
      result.push_back((*it).second); 
     } 
    } else { 
     result.insert(result.end(),digit); 
    } 

    return result; 
} 

void showPermutations(vector<string> &perms) { 
    vector<string>::iterator it; 
    for (it = perms.begin(); it != perms.end(); it++) { 
     cout << *it << endl; 
    } 
} 


vector<string> getPermutations(const string &phoneNumber,const multimap<char,char> &lmap) { 
    vector<string> results; 

    string number = phoneNumber; 
    vector<char>::iterator vcit; 
    vector<char> letters; 
    unsigned int i; 

    for (i=0;i<phoneNumber.length();i++) { 
     letters = getLetters(number[i],lmap); 
     for (vcit=letters.begin();vcit!=letters.end();vcit++) { 
      number[i] = *vcit; 
      results.push_back(number); 
     } 
    } 


    return results; 
} 

int main() { 

    multimap<char,char> lmap; 
    initLetterMap(lmap); 

    string input; 

    cout << "Enter a phone number to get all possible vanity numbers" << endl; 
    cout << "> "; getline(cin,input); 

    showPermutations(getPermutations(input,lmap)); 


    return 0; 
} 

tôi nhận được một loạt toàn bộ các vấn đề xây dựng khi tôi cố gắng xây dựng này, và không chắc chắn làm thế nào để giải quyết hầu hết trong số họ:

In file included from /usr/include/c++/4.0.0/backward/multimap.h:59, 
from phone02.cpp:18: 
/usr/include/c++/4.0.0/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the <X> header for the <X.h> header for C++ includes, or <iostream> instead of the deprecated header <iostream.h>. To disable this warning use -Wno-deprecated. 
/usr/include/c++/4.0.0/bits/stl_pair.h: In constructor 'std::pair<_T1, _T2>::pair(const std::pair<_U1, _U2>&) [with _U1 = std::_Rb_tree_const_iterator<std::pair<const char, char> >, _U2 = std::_Rb_tree_const_iterator<std::pair<const char, char> >, _T1 = std::_Rb_tree_iterator<std::pair<const char, char> >, _T2 = std::_Rb_tree_iterator<std::pair<const char, char> >]': 
phone02.cpp:75: instantiated from here 
/usr/include/c++/4.0.0/bits/stl_pair.h:90: error: no matching function for call to 'std::_Rb_tree_iterator<std::pair<const char, char> >::_Rb_tree_iterator(const std::_Rb_tree_const_iterator<std::pair<const char, char> >&)' 
/usr/include/c++/4.0.0/bits/stl_tree.h:167: note: candidates are: std::_Rb_tree_iterator<_Tp>::_Rb_tree_iterator(std::_Rb_tree_node<_Tp>*) [with _Tp = std::pair<const char, char>] 
/usr/include/c++/4.0.0/bits/stl_tree.h:164: note: std::_Rb_tree_iterator<_Tp>::_Rb_tree_iterator() [with _Tp = std::pair<const char, char>] 
/usr/include/c++/4.0.0/bits/stl_tree.h:152: note: std::_Rb_tree_iterator<std::pair<const char, char> >::_Rb_tree_iterator(const std::_Rb_tree_iterator<std::pair<const char, char> >&) 
/usr/include/c++/4.0.0/bits/stl_pair.h:90: error: no matching function for call to 'std::_Rb_tree_iterator<std::pair<const char, char> >::_Rb_tree_iterator(const std::_Rb_tree_const_iterator<std::pair<const char, char> >&)' 
/usr/include/c++/4.0.0/bits/stl_tree.h:167: note: candidates are: std::_Rb_tree_iterator<_Tp>::_Rb_tree_iterator(std::_Rb_tree_node<_Tp>*) [with _Tp = std::pair<const char, char>] 
/usr/include/c++/4.0.0/bits/stl_tree.h:164: note: std::_Rb_tree_iterator<_Tp>::_Rb_tree_iterator() [with _Tp = std::pair<const char, char>] 
/usr/include/c++/4.0.0/bits/stl_tree.h:152: note: std::_Rb_tree_iterator<std::pair<const char, char> >::_Rb_tree_iterator(const std::_Rb_tree_iterator<std::pair<const char, char> >&) 
make: *** [phone02.o] Error 1 

các số dòng là một chút đi, nhưng những người quan trọng mà tôi có thể nhìn thấy là hai khoảng no matching function for call to 'std::_Rb_tree_iterator<std::pair<const char, char> >::_Rb_tree_iterator(const std::_Rb_tree_const_iterator<std::pair<const char, char> >&)'

Bên cạnh lỗi, tôi cũng tin rằng tôi đang đi sai hướng với thuật toán của mình.

Vì vậy, tôi có 2 câu hỏi ở đây:

1. Tại sao tôi lại nhận được những xây dựng sai sót, và làm thế nào để khắc phục chúng?
2. Bạn sẽ đề xuất cách giải quyết vấn đề này như thế nào? Tôi có đi đúng hướng hay không?

Đối với câu hỏi # 2, Tôi không muốn nhận các giải pháp, chỉ cần lời khuyên hoặc con trỏ đi đúng hướng.

Cảm ơn!

PS: Tôi đang xây dựng này trên Mac OS X 10.5.8 với gcc, sử dụng QtCreator 1.2.1

UPDATE:

tôi đã biên soạn thành công một chương trình giải pháp. Tôi sẽ đăng mã nguồn cho những người tò mò.

#include <iostream> 
#include <map> 
#include <vector> 
#include <string> 

using namespace std; 

void initLetterMap(map<char,string> &lmap); 
vector<string> getMapped(const string &phoneNumber, map<char,string> &lmap); 
vector<string> getPermutations(vector<string> number); 
unsigned long int countPermutations(vector<string> number); 

void initLetterMap(map<char,string> &lmap) { 
    lmap['0'] = "0"; 
    lmap['1'] = "1"; 
    lmap['2'] = "2ABC"; 
    lmap['3'] = "3DEF"; 
    lmap['4'] = "4GHI"; 
    lmap['5'] = "5JKL"; 
    lmap['6'] = "6MNO"; 
    lmap['7'] = "7PQRS"; 
    lmap['8'] = "8TUV"; 
    lmap['9'] = "9WXYZ"; 
} 

unsigned long int countPermutations(vector<string> number) { 
    long int fold = 1; 
    int vals = 0; 
    vector<string>::iterator it; 
    for (it=number.begin();it!=number.end();it++) { 
     vals = (*it).length(); 
     fold *= vals; 
    } 
    return fold; 
} 

vector<string> getMapped(const string &phoneNumber, map<char,string> &lmap) { 
    unsigned int i; 
    vector<string> out; 
    char digit; 
    string temp; 
    for (i=0;i<phoneNumber.length();i++) { 
     digit = phoneNumber.at(i); 
     if (isdigit(digit)) { 
      out.push_back(lmap[digit]); 
     } else { 
      temp = string(1,digit); 
      out.push_back(temp); 
     } 
    } 
    return out; 
} 

vector<string> getPermutations(vector<string> number) { 
    vector<string> results; 

    unsigned long int i,j,k; 
    unsigned long int perms = countPermutations(number); 

    vector<string>::reverse_iterator numit; 
    string temp,temp2; 


    vector<int> state = vector<int>(number.size(), 0); 
    vector<int>::reverse_iterator stateit; 

    for (i=0;i<perms;i++) { 
     j=i; 
     temp = ""; 
     for (stateit=state.rbegin(), numit=number.rbegin();stateit!=state.rend();stateit++, numit++) { 
      *stateit = j % (*numit).length(); 
      j /= (*numit).length(); 
      temp.insert(temp.begin(),(*numit)[*stateit]); 
     } 
     results.push_back(temp); 
    } 


    return results; 
} 

int main() { 
    map<char,string> lettermap; 
    initLetterMap(lettermap); 

    string input; 

    cout << "> "; getline(cin,input); 

    vector<string> perms = getPermutations(getMapped(input,lettermap)); 
    vector<string>::iterator it; 
    for (it=perms.begin();it!=perms.end();it++) { 
     cout << *it << endl; 
    } 
} 

Mã này có lẽ phức tạp hơn so với trước đây, nhưng mục tiêu của tôi là chỉ làm cho nó hoạt động. Dường như nó chạy khá nhanh với 10 số điện thoại, vì vậy tôi đoán nó không quá tệ.

Nhờ Jacob và ShreevatsaR đã giúp tôi chỉ đúng hướng!

Answer 1

Vâng, nếu bạn không muốn có một giải pháp, tôi sẽ thực hiện nó như thế này:

Sử dụng một vector V với mỗi yếu tố được rút ra từ một chuỗi. Ví dụ. nếu đó là 23, sau đó vectơ V của bạn, sẽ có hai vectơ mỗi cái chứa 2ABC và 3DEF.

Lặp lại từng chữ số như bộ đếm thông qua chuỗi được liên kết. Di chuyển từ phải sang trái và khi mỗi dòng chữ số tràn sang bên trái, và đặt lại, v.v.

Hiển thị bộ đếm tại mọi lần lặp để có được "số" của bạn.

Answer 2

Gợi ý để biên dịch lỗi:

1. không có tập tin gọi là <multimap.h> trong STL. nó phải là <map>
2. Vấn đề là với chức năng getLetters. multimaplmap đã được chuyển bởi tham chiếu const.Do đó, equal_range API trên lmap sẽ trả lại cặp const_iterator không chỉ iterator.

Answer 3

Làm thế nào về những điều sau đây:

#include <cstddef> 
#include <iostream> 
#include <iterator> 
#include <string> 
#include <algorithm> 

template <typename Iterator> 
bool next_combination(const Iterator first, Iterator k, const Iterator last); 

int main() 
{ 
    std::string phone_number = "23"; 

    std::string number[] = { 
          "0", "1", "2abc", "3def", "4ghi", 
          "5jkl","6mno", "7pqrs", "8tuv","9wxyz" 
          }; 

    std::string tmp_set; 
    std::string set; 

    for(std::size_t i = 0; i < phone_number.size(); ++i) 
    { 
     tmp_set += number[static_cast<std::size_t>(phone_number[i] - '0')]; 
    } 
    std::sort(tmp_set.begin(),tmp_set.end()); 

    std::unique_copy(tmp_set.begin(), 
        tmp_set.end(), 
        std::back_inserter(set)); 

    std::string current_set; 
    current_set.reserve(phone_number.size()); 

    do 
    { 
     std::copy(set.begin(), 
       set.begin() + phone_number.size(), 
       std::back_inserter(current_set)); 
     do 
     { 
     std::cout << current_set << std::endl; 
     } 
     while (std::next_permutation(current_set.begin(),current_set.end())); 
     current_set.clear(); 
    } 
    while(next_combination(set.begin(), 
          set.begin() + phone_number.size(), 
          set.end())); 
    return 0; 
} 


    template <typename Iterator> 
    inline bool next_combination(const Iterator first, Iterator k, const Iterator last) 
    { 
     /* Credits: Thomas Draper */ 
     if ((first == last) || (first == k) || (last == k)) 
     return false; 
     Iterator itr1 = first; 
     Iterator itr2 = last; 
     ++itr1; 
     if (last == itr1) 
     return false; 
     itr1 = last; 
     --itr1; 
     itr1 = k; 
     --itr2; 
     while (first != itr1) 
     { 
     if (*--itr1 < *itr2) 
     { 
      Iterator j = k; 
      while (!(*itr1 < *j)) ++j; 
      std::iter_swap(itr1,j); 
      ++itr1; 
      ++j; 
      itr2 = k; 
      std::rotate(itr1,j,last); 
      while (last != j) 
      { 
       ++j; 
       ++itr2; 
      } 
      std::rotate(k,itr2,last); 
      return true; 
     } 
     } 
     std::rotate(first,k,last); 
     return false; 
    } 

Answer 4

Dưới đây đang chứng minh làm thế nào để làm điều đó trong bước đơn giản (đệ quy):

1.) Tạo vector của chuỗi, và đẩy chuỗi đại diện cho "nhân vật càng tốt kết quả từ việc nhấn phím đó "(0-key đến 9-key).

2.) Vì mỗi lần nhấn phím sẽ chỉ thêm một char vào chuỗi kết quả, chỉ chắp thêm một ký tự cùng một lúc và gọi hàm đệ quy cho lần nhấn phím tiếp theo. Làm điều đó cho mỗi char có thể tại phím đó.

Demo:

void getCombination(vector<string> &combinations, string current, const string &A, int idx, const vector<string> &keyset){ 
     if(idx >= A.size()) { 
      combinations.push_back(current); 
      return; 
     } 
     int key = (A[idx] - '0'); 
     int len = keyset[key].length(); 

     for(int i = 0; i < len; i++){ 
      current.push_back(keyset[key][i]); //pick at once one char corresp. to that keypress 
      getCombination(combinations, current, A, idx+1, keyset); 
      current.pop_back(); 
     } 
} 

vector<string> letterCombinations(string A) { 
    vector<string> combinations; 
    vector<string> keyset{"0", "1", "2abc", "3def", "4ghi", "5jkl", "6mno", "7pqrs", "8tuv", "9wxyz"}; 
    getCombination(combinations, std::string({}), A, 0, keyset); 
    return combinations; 
} 

int main() { 
    vector<string> combinations = letterCombinations("23"); 
    for(string word : combinations){ 
     cout << word << ", "; 
    } 
    return 0; 
} 

Cho Output: 23, 2d, 2e, 2f, a3, quảng cáo, ae, af, b3, bd, được, bf, c3, cd, ce, cf,