Permutacje liter i cyfr w numerze telefonu

Question

Dla mojej klasy informatycznej, musimy napisać program (w języku C++), który pobiera dane wejściowe i wyprowadza możliwe kombinacje według klawiatury w telefonie, pozostawiając znaki nie będące cyframi.

Na przykład, wprowadzając 2 wyjścia 2, A, B, C. Wprowadzanie 23 wyjść 23, A3, B3, C3, 2D, 2E, 2F, AD, AE, AF, BD, BE, BF itd.

Aplikacja przewidziana dla tego programu polega na znajdowaniu permutacji numerów "toaletowych" dla danego numeru telefonu.

Obecnie program Pisałem nawet nie skompilować, a obawiam się, że algorytm używam jest niepoprawna:

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

dostaję całe mnóstwo kwestii budowania gdy próbuję budować to, i nie wiem, jak rozwiązać większość z nich:

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 

numery linii są trochę off, ale ważne te, które widzę są dwa o 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> >&)'

Oprócz błędów uważam, że zmierzam w niewłaściwym kierunku z moim algorytmem.

Więc mam 2 pytania tutaj:

1. Dlaczego otrzymuję je zbudować błędy i jak je naprawić?
2. Jak zasugerowałbyś rozwiązanie tego problemu? Czy jestem na dobrej drodze, czy nie?

Na pytania nr 2, wolałbym nie dostać rozwiązań, tylko porady i wskazówki we właściwym kierunku.

Dzięki!

PS: buduję ten Mac OS X 10.5.8 z gcc, przy użyciu Qt Creator 1.2.1

UPDATE:

Mam pomyślnie skompilowany program rozwiązania. Prześlę kod źródłowy tym, którzy są ciekawi.

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

Kod jest prawdopodobnie bardziej skomplikowany, niż powinien być, ale moim celem było sprawienie, by działał. Wydaje się, że działa dość szybko dla 10-cyfrowych numerów telefonów, więc domyślam się, że nie jest tak źle.

Podziękowania dla Jacoba i ShreevatsyR za skierowanie mnie we właściwym kierunku!

Answer 1

Dobrze, jeśli nie chcą rozwiązania, chciałbym wdrożyć go tak:

Użyj wektor v z każdego elementu poprowadzoną od łańcucha. Na przykład. jeśli jest 23, to twój wektor V miałby dwa wektory, z których każdy zawierałby 2ABC i 3DEF.

Powtarzaj każdą cyfrę jak licznik za pomocą powiązanego ciągu. Przesuń od prawej do lewej, a gdy każda cyfra przepełni się, zwiększ ją w lewo i zresetuj itd.

Wyświetl licznik w każdej iteracji, aby uzyskać "numer".

Answer 2

Podpowiedź skompilować błędy:

1. nie ma pliku o nazwie <multimap.h> w STL. powinien być <map>
2. Problem dotyczy funkcji getLetters. multimaplmap został przekazany przez odniesienie do stałej.W związku z tym equal_range API pod numerem lmap zwróci parę const_iterator nie tylko iterator.

Answer 3

Jak o następujące elementy:

#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

poniższy kod wykazać, jak to zrobić w kilku prostych krokach (rekurencyjnie):

1.) Utwórz wektor ciągów i naciskać struny, które oznacza: „możliwych znaków wynikający z tego naciśnięcia klawisza "(0-klawisz na 9-klawisz).

2.) Ponieważ każde naciśnięcie klawisza spowoduje dodanie TYLKO jednego znaku do łańcucha wynikowego, dodanie tylko jednego znaku naraz i wywołanie funkcji rekurencyjnie dla następnego naciśnięcia klawisza. Zrób to dla każdego możliwego znaku na tym naciśnięciu klawisza.

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

Daje wyjściowy: 23, 2d, 2e, 2f, a3, reklama, AE, AF, b3, bd, być bf, c3, CD, CE, CF