ansaurus

Question

Permutations of letters and numbers in a phone number.

Answer 1

+1 A:

Hint to compile errors:

there is no file called <multimap.h> in STL. it should be <map>
The problem is with getLetters function. multimap lmap has been passed by const reference. Hence, equal_range API on lmap would return pair of const_iterator not just iterator.

aJ 2009-10-06 03:17:37

Thanks, that took care of the initial errors. When I fixed that some others cropped up. After some fiddling, I got it to compile, and confirmed that my algorithm is all wrong.

Austin Hyde 2009-10-06 03:55:03

Answer 2

A:

Well if you don't want a solution, I would implement it like this:

Use a vector V with each element drawn from a string. E.g. if it's 23, then your vector V, would have two vectors each containing 2ABC and 3DEF.

Iterate each digit like a counter through the associated string. Move right-to-left and when each digit overflows increment the one to the left, and reset, etc.

Display the counter at every iteration to obtain your "number".

Jacob 2009-10-06 03:22:17

+1, this is the best way of doing it without using recursion. (Using recursion probably makes for the neatest code...)

ShreevatsaR 2009-10-06 07:49:14

Hmmm .. cowardly downvotes - *leave a note!*

Jacob 2010-01-09 02:42:16

Answer 3

+6 A:

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 = "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>
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;
}

Beh Tou Cheh 2009-10-06 03:46:30

Besides the fact I wasn't looking for a solid solution, it looks fine, but a bit too complex for me...

Austin Hyde 2009-10-06 03:52:17

ansaurus

tags:

views:

answers:

Permutations of letters and numbers in a phone number.

related questions