## Alphabetic Phone Number Generator SOLVED [Problem of the Week]

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<

#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

for(int j = 0 ; j

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

Thanks everyone 😀

[…] the problem solution here […]

Alphabetic Phone Number Generator [Problem of the Week] « AlaaShaker’s WeblogOctober 18, 2008 at 6:12 am

I love your site!

_____________________

Experiencing a slow PC recently? Fix it now!

Michael TimFebruary 28, 2009 at 7:16 pm

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

Money BloggingJune 11, 2010 at 1:21 pm

You have a small error in your 1st code:

sol solution (either make them all ‘sol’ or ‘solution’).

Thanks, great site!

OlliApril 27, 2011 at 10:11 am