AlaaShaker's Weblog

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 <iostream>
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<<sol[j];
        cout<<endl;
        return;
    }
    for (int j=0; j<5; j++)
    {
        if(!visited[j])
        {
            visited[j] = true;
            sol[i] = j;
            Permute(i+1);
            visited[j] = false;
        }
    }
}
int main()
{
   for(int i=0 ;i<5 ;i++)
        visited[i] = false;
    Permute(0);
    cout<<"Count: "<<count<<endl;
    return 0;
}

Now comes the transformation time!
The only difference now is that we won’t be marking a digit, then permute the left N-1 digits. We’ll be marking a character of the 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 <iostream>
#include <fstream>
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<strlen(number); j++)
            cout<<sol[j];
        cout<<endl;
        return;
    }
    int t = number[i] - '0';
    int j=i;
    {
        for(int k = 0; k<3; k++)
        {
            if(!vis[t][k])
            {
                vis[t][k] = true;
                sol[i] = dict[t][k];
                Permute(i+1, number);
                vis[t][k] = false;
            }
        }
    }
} 

int main()
{
    char number[SIZE];
    cout<<"Enter up to "<<SIZE<<" digit phone number: ";
    cin>>number; 

   for(int j = 0 ; j<strlen(number); j++)
        for(int k = 0; k<3; k++)
            vis[j][k] = false; 

    Permute(0, number);
    cout<<"Total: "<<count<<endl;
    return 0;
}

WINNERS FOR THIS PROBLEM:

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

Thanks everyone