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

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:我使用QtCreator 1.2.1在Mac OS X 10.5.8和gcc上构建它

更新:

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

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

Answer 2

好吧，如果你不需要解决方案，我会这样实现：

使用向量 V，每个元素都从字符串中提取。例如，如果它是 23，那么您的向量 V 将有两个向量，每个向量包含 2ABC 和 3DEF。

像计数器一样通过关联的字符串迭代每个数字。从右向左移动，当每一位数字溢出时，向左递增一位，然后重置，等等。

在每次迭代时显示计数器以获得您的“数字”。