Rearrangement of letters and numbers in a telephone number

Question

For my informatics class, we need to write a program (in C ++) that takes character input and displays possible permutations according to the typing keyboard on the phone, leaving obscure characters in place.

For example, entering 2 outputs 2, A, B, C. Entering 23 outputs 23, A3, B3, C3, 2D, 2E, 2F, AD, AE, AF, BD, BE, BF, etc.

The application provided for this program is to search for permutations of vanity phone numbers for a given phone number.

Currently, the program I wrote doesn't even compile, and I'm afraid that the algorithm I'm using is incorrect:

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

I get a lot of build problems when I try to build this and don’t know how to solve most of them:

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 :

• ?
• ? ?

№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- , , .

, !

Answer 1

, , :

V , . . 23, V , 2ABC 3DEF.

. , , reset ..

, "".

Answer 2

:

#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 3

:

• STL <multimap.h>. <map>
• getLetters. multimap lmap const. , equal_range API lmap const_iterator iterator.

Answer 4

, ():

1.) , " , " (0- 9-).

2.) char , . char .

:

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,