電話號碼中字母和數字的排列

Question

對於我的計算機科學課，我們需要編寫一個程序（使用C++），它接受字符輸入並根據手機上的撥號盤輸出可能的排列組合，留下非數字字符。例如，輸入2個輸出2，A，B，C。輸入23個輸出23，A3，B3，C3,2D，2E，2F，AD，AE，AF，BD，BE，BF等。

該程序提供的應用程序爲給定的電話號碼查找「虛榮」電話號碼的排列組合。

目前，我寫的程序甚至不編譯，我怕我使用的算法不正確：

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

我得到的構建問題，整體轉換，當我嘗試建立這一點，我不知道如何解決大部分：

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 

行號是有點過了，但我可以看到重要的是兩個約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> >&)'

除了這些錯誤之外，我還相信我正在用我的算法向錯誤的方向前進。

所以我有2個問題在這裏：

1. 爲什麼會出現這些構建錯誤，以及如何解決這些問題？
2. 你會如何解決這個問題？我在正確的軌道上還是沒有？

對於問題＃2，我寧願沒有得到解決方案，只是建議或指針在正確的方向。

謝謝！

PS：我建立這個在Mac OS X 10.5.8用gcc，使用QtCreator 1.2.1

UPDATE：

我已成功編輯瞭解決方案。我會將源代碼發佈給那些好奇的人。

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

該代碼可能比它更復雜，但我的目標是讓它工作。對於10位數的電話號碼，它似乎運行得相當快，所以我猜這不算太糟糕。

感謝Jacob和ShreevatsaR讓我指出正確的方向！

Answer 1

好吧，如果你不想要一個解決方案，我會實現它是這樣的：

使用矢量V與字符串繪製的每個元素。例如。如果它是23，那麼你的向量V將有兩個向量，每個向量包含2ABC和3DEF。

通過關聯的字符串像計數器一樣迭代每個數字。從右向左移動，當每個數字溢出時，向左遞增，然後重置等。

在每次迭代中顯示計數器以獲取您的「編號」。

Answer 2

提示編譯錯誤：

1. 沒有叫<multimap.h>在STL文件。應該是<map>
2. 問題出在getLetters函數。 multimaplmap已被const引用傳遞。因此，equal_range API lmap將返回一對const_iterator不僅iterator。

Answer 3

如何如下：

#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

下面的代碼演示瞭如何做簡單的步驟（遞歸）：

1）創建的字符串的載體，推動代表「可能的字符的字符串由此按鍵產生「（0鍵至9鍵）。

2.）由於每個按鍵都只會向結果字符串添加一個字符，所以一次只能添加一個字符，並遞歸調用下一個按鍵。在按鍵時爲每個可能的字符做它。

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

給出輸出： 23，2D，2E，2F，A3，AD，AE，AF，B3，BD，BE，BF，C3，CD，CE，CF，