AlaaShaker's Weblog

// untitled …

Alphabetic Phone Number Generator SOLVED [Problem of the Week]

with 4 comments

It’s been a while, huh? Well, for the second time, my apologies!

Anyway, the past problem was of medium difficulty, but there’s a trick that could make your life much easier. Do you know what a permutation is? This is a permutation problem. A definition of permutation is that a permutation of [ABC] is simply [ABC – ACB – BAC – BCA – CAB – CBA] .. all possible arrangements of the three letters. Think of our problem the same way, you just need all possible arrangements for the three characters corresponding to each number. Easier? Thanks to Abdalla Gamal for making our lives easier.

So, similar to the ACM problems, we’ll solve the standard permutation problem, where we get to print all possible arrangements of a set of digits. Then, we transform that to our problem.

Let’s start with a permutation of 5 digits (producing 01234, 01243, 01324, 01342, etc). The idea behind the following recursive code is based on holding two arrays: visited and solution. For each position of the 5 positions, we mark one of the 5 digits as visited (by setting visited[x] = true where x [0-4]), place it in the solution array, then try to place 4 more digits by calling the same function with one added to an index (position). The problem now becomes a permutation of the 4 left digits, and so on …

#include
using namespace std;

bool visited[8];
int solution[8];
int count = 0;

void Permute(int i)
{
if(i >= 5)
{
count++;
for(int j=0; j<5; j++) cout<three characters that correspond that digit, try complete the rest of the string, then after the recursion is done, we unmark it, and move on to the next character, and so on ..

#include
#include
using namespace std;

#define SIZE 10
// Uncomment these two lines if you want to print to a file
// instead of printing to the console screen ..
// ofstream fout(“output.txt”);
// #define cout fout

char dict[SIZE][3] = {
{‘a’, ‘b’, ‘c’}, // 0
{‘d’, ‘e’, ‘f’}, // 1
{‘g’, ‘h’, ‘i’}, // 2
{‘j’, ‘k’, ‘l’}, // 3
{‘m’, ‘n’, ‘o’}, // 4
{‘p’, ‘q’, ‘r’}, // 5
{‘s’, ‘t’, ‘u’}, // 6
{‘v’, ‘w’, ‘x’}, // 7
{‘y’, ‘z’, ‘A’}, // 8
{‘B’, ‘C’, ‘D’} // 9
};

char sol[8];
bool vis[SIZE][3];
int count = 0;

void Permute(int i, char* number)
{
if(i >= strlen(number))
{
count++;
for(int j = 0; j>number;

for(int j = 0 ; jWINNERS FOR THIS PROBLEM:

  • TeCNoYoTTa
  • Metal_
  • Mohamed Hesham
  • Tasniem Seliem
  • Amal Hussein
  • 5olio

Thanks everyone 😀

Advertisements

Written by AlaaShaker

October 18, 2008 at 6:09 am

4 Responses

Subscribe to comments with RSS.

  1. […] the problem solution here […]

  2. I love your site!

    _____________________
    Experiencing a slow PC recently? Fix it now!

    Michael Tim

    February 28, 2009 at 7:16 pm

  3. I find myself coming back here a lot to read. I have learned much new things here. Thanks a lot!

    Money Blogging

    June 11, 2010 at 1:21 pm

  4. You have a small error in your 1st code:
    sol solution (either make them all ‘sol’ or ‘solution’).

    Thanks, great site!

    Olli

    April 27, 2011 at 10:11 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: