Перестановки букв и цифр в номере телефона

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-значных телефонных номеров, так что, думаю, это не так уж и плохо.

Спасибо Джейкобу и Шриватсару за то, что они указали мне правильное направление!

Answer 1

Как насчет следующего:

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

Ну, если вам не нужно решение, я бы реализовал его так:

Используйте вектор V с каждым элементом, взятым из строки. Например. если это 23, то ваш вектор V будет иметь два вектора, каждый из которых содержит 2ABC и 3DEF.

Итерация каждой цифры как счетчика через связанную строку. Перемещение вправо-влево, при переполнении каждой цифры увеличивается значение влево, сбрасывание и т. Д.

Отображать счетчик на каждой итерации, чтобы получить ваш «номер».

Answer 3

Подсказка к ошибкам компиляции:

1. В STL нет файла с именем <multimap.h>. должно быть <map>
2. Проблема с функцией getLetters. multimap lmap передано по постоянной ссылке. Следовательно, equal_range API на lmap вернет пару const_iterator, а не только iterator.

Answer 4

Ниже приведен код, демонстрирующий, как это сделать простыми шагами (рекурсивно):

1.) Создайте вектор строк и вставьте строки, представляющие «возможные символы, возникающие в результате нажатия этой клавиши» (клавиши от 0 до 9).

2.) Поскольку каждое нажатие клавиши будет служить для добавления ТОЛЬКО одного символа в результирующую строку, добавляйте только один символ за раз и рекурсивно вызывайте функцию для следующего нажатия клавиши. Сделайте это для каждого возможного символа при нажатии этой клавиши.

Демо

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,