c++ - 电话号码中字母和数字的排列

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> >&)' 的两个

除了错误之外，我还认为我的算法正朝着错误的方向前进。

所以我在这里有两个问题:

1. 为什么会出现这些构建错误，我该如何解决？
2. 您建议如何解决这个问题？我是否在正确的轨道上？

对于问题 #2，我不希望得到解决方案，只是建议或正确方向的指示。

谢谢!

PS:我在 Mac OS X 10.5.8 上用 gcc 构建这个，使用 QtCreator 1.2.1

更新:

我已经成功地编译了一个解决方案。我会将源代码发布给那些好奇的人。

#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

以下情况如何:

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