How to generate all the different values in converting a number into a phone vanity letter in C++

Question

Hello, the C++ assignment im working on is to ask the user for a 4 digit number and then the program outputs all the possible vanity letters based on a phone keypad. I am currently stuck on the best way to get the program to work and how to write it. Anyone got any ideas? thanks for the help!

Answer 1

This sounds homework-ish, so I'll only give you an idea:

You need a mapping from each number to the corresponding set of letters. Then you generate the possible permutations for all the different letters corresponding to the respective digits.

For example, for the digit "1", the possible letters are 'A', 'B', and 'C', for the digit "2" they are 'D', 'E', and 'F'. so for the number "12" the possible permutations would be

AD
AE
AF
BD
BE
BF
CD
CE
CF

Does this help?

Answer 2

Pseudo code:

main(char[] input) {
  for(int i = 0 .. 3) { letters[i] = letters(input[i]) };

  for(int i = 0 .. letters[0].length) {
    for(int j = 0 .. letters[1].length) {
      for(int k = 0 .. letters[2].length) {
        for(int l = 0 .. letters[3].length) {
          print(letters[0][i], letters[1][j], letters[2][k], letters[3][l]);
        }
      }
    }
  }
}

char[] letters(char digit) {
  switch (digit) {
    case '2' : {'a', 'b', 'c'};
    ..
    case '9' : {'w', 'x', 'y', 'z'};
  }
}

Answer 3

Every 4 digit sequence of vanity letters is a vanity letter followed by a 3-digit sequence of vanity letters. Does that give you an idea of how to break it down?

Answer 4

My C++ is a bit rusty, but this should get you pretty close. The idea here is to use a combination of looping and recursion. The recursion depth is equal to the length of the phone number, and each level of recursion generates the possible permutations for that and subsequent digits of the phone number.

The code itself is easy - understanding why it works is the hard part :)

std::map<char,std::string> letters = new std::map<char,std::string>();
letters.put('1', "ABC");
letters.put('2', "DEF");
... etc ...

std::vector<std::string> all_permutations = new std::vector<std::string>();

void GeneratePermutations( std::string number, int digit, std::string vanity) {
   std::string letters_for_number = letters.get(number[digit - 1]);

   for( int i = 0; i < letters_for_number.size(); i++ ) {
      vanity += letters_for_number[i];
      if ( digit < number.length() ) {
         GeneratePermutations(number, digit + 1, vanity);
      } else {
         all_permutations.add(vanity);
      }
   }
}

void main() {
    GeneratePermutations("1234", 1, "");
}

Answer 5

How about the following:

#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 = "12";

   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>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}