Permutazioni di lettere e numeri in un numero di telefono

Question

Per la mia classe di informatica, è necessario scrivere un programma (in C++) che prenda un input di caratteri e ne restituisca le possibili permutazioni secondo la tastiera di un telefono, lasciando caratteri non numerici in posizione.

Ad esempio, immissione di 2 uscite 2, A, B, C. Ingresso 23 uscite 23, A3, B3, C3, 2D, 2E, 2F, AD, AE, AF, BD, BE, BF, ecc.

L'applicazione fornita per questo programma sta trovando le permutazioni dei numeri di telefono "vanity" per un determinato numero di telefono.

Attualmente, il programma che ho scritto non ha nemmeno compilare, e temo l'algoritmo che sto utilizzando non è corretta:

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

ottengo tutta una serie di problematiche di compilazione quando si tenta di costruire questo, e non sono sicuro di come risolvere la maggior parte di loro:

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 

i numeri di riga sono un po 'fuori, ma quelli importanti che posso vedere sono i due circa 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> >&)'

Oltre agli errori, credo anche che mi stia dirigendo nella direzione sbagliata con il mio algoritmo.

Così ho 2 domande qui:

1. Perché ricevo questi errori di generazione, e come faccio a riparare?
2. Come suggeriresti di risolvere questo problema? Sono sulla buona strada o no?

Per la domanda # 2, preferirei non avere soluzioni, proprio consiglio o puntatori nella giusta direzione.

Grazie!

PS: Sto costruendo questo su Mac OS X 10.5.8 con gcc, utilizzando QtCreator 1.2.1

UPDATE:

ho compilato con successo un programma di soluzione. Pubblicherò il codice sorgente per coloro che sono curiosi.

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

Il codice è probabilmente più complicato di quanto deve essere, ma il mio obiettivo era quello di farlo funzionare. Sembra funzionare abbastanza velocemente per numeri di telefono a 10 cifre, quindi immagino che non sia troppo male.

Grazie a Jacob e ShreevatsaR per avermi indicato nella giusta direzione!

Answer 1

Beh, se non si vuole una soluzione, vorrei implementare in questo modo:

Utilizzare un vettore V con ogni elemento tratto da una stringa. Per esempio. se è 23, quindi il vettore V, avrebbe due vettori contenenti ciascuno 2ABC e 3DEF.

Iterare ciascuna cifra come un contatore attraverso la stringa associata. Sposta da destra a sinistra e quando ogni cifra trabocca incrementa quella a sinistra e ripristina, ecc.

Visualizza il contatore ad ogni iterazione per ottenere il "numero".

Answer 2

Avvertenza per errori di compilazione:

1. non v'è alcun file chiamato <multimap.h> in STL. dovrebbe essere <map>
2. Il problema è con la funzione getLetters. multimaplmap è stato passato da riferimento const.Quindi, l'API equal_range su lmap restituirebbe coppia di const_iterator non solo iterator.

Answer 3

Come circa la seguente:

#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

Di seguito il codice dimostrano come farlo in semplici passi (ricorsivamente):

1.) Creare vettore di stringhe, e spingere le stringhe che rappresenta "caratteri possibili risultante da quella pressione di tasto "(da 0 a 9 tasti).

2.) Poiché ogni pressione di un tasto servirà ad aggiungere SOLO un carattere alla stringa risultante, aggiungere un solo carattere alla volta e chiamare la funzione in modo ricorsivo per la pressione del tasto successivo. Fallo per ogni possibile carattere a quel tasto.

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

Dà in uscita: 23, 2d, 2e, 2f, a3, annuncio, AE, AF, b3, bd, essere, bf, c3, cd, ce, cf,