CareerCup

A recursive algorithm for generating permutations.

//normal backtracking
void generate(string phonenum,vector<string> digit2letter,char* result,int resultsize,int idx)
{
if(idx==phonenum.size()){
cout<<result<<"\n";
return;
}
for(int i=0;i<digit2letter[idx].size();i++)
{
result[resultsize]=digit2letter[idx][i];
generate(phonenum,digit2letter,result,resultsize+1,idx+1);
result[resultsize]='\0';
}
}

//call with generate(phonenum,digit2letter,result,0,0);

I am not sure about time complexity...someone tell me plzz.

Are you sure we need to print all the possible strings that can be generated from the given 9 digit phone number ?? If this being the case then there will be infinite strings.

Here's some tested code:

/**
 * PhoneChar.cc
 * (c) souravgh@usc.edu
 * Sat Feb 12 1423
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stack>

using namespace std;
using namespace __gnu_cxx;

// Recursive procedure which inspects each possible permutation
// of strings formable using the digits given in inputCharPtr.
// inputCharPtr: The string containing the no. eg. "234"
void printChars (char *inputCharPtr);

int main () {
  char inputCharPtr[10];

  scanf ("%s", inputCharPtr);

  printChars (inputCharPtr);

  return EXIT_SUCCESS;
}

const char *digitLetterMapCharPtrPtr[] = {"+", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
stack <char> charStack;

// Print the entire string contained in the charStack
void printStack ();

// Recursive procedure which inspects each possible permutation
// of strings formable using the digits given in inputCharPtr.
// inputCharPtr: The string containing the no. eg. "234"
void printChars (char *inputCharPtr) {
  if (!inputCharPtr[0]) {
    printStack ();
    return;
  }

  // Get the int representation of the current digit.
  // Need this to index the digitLetterMapCharPtrPtr array.
  int currentDigitInt = *inputCharPtr - '0';

  // We start from the first character and inspect each character
  // calling the procedure recursively with the next character.
  for (int indexInt = 0; 
       indexInt < (int)strlen (digitLetterMapCharPtrPtr[currentDigitInt]); 
       indexInt++) {
    charStack.push (digitLetterMapCharPtrPtr[currentDigitInt][indexInt]);
    printChars (inputCharPtr + 1);
    charStack.pop ();
  }
}

// Print the entire string contained in the charStack
void printStack () {
  stack <char> tempCharStack;

  // Reverse the stack.
  for( ; charStack.size (); charStack.pop ()) {
    tempCharStack.push (charStack.top ());
  }

  printf ("=> ");

  // Restore and print out the stack.
  for ( ; tempCharStack.size (); tempCharStack.pop ()) {
    printf ("%c", tempCharStack.top ());
    charStack.push (tempCharStack.top ());
  }

  printf ("\n");
}

The complexity in this case depends on the no. of output permutations. To that effect I feel it's something like: O (3^n), where n is the length of the input string e.g. "234". (Why 3? Each digit has 3 possible characters associated with it. All except 0, 1, 7, 9).

char *num[] ={ "abc",
"def",
"ghi",
"jkl",
"mno",
"pqr",
"stu",
"vwx",
"yz"
};


void printallperm1(int p[10], int q[10] , char *b ,int l , int k, char *ss)
{
if( k == l )
{
*b = '\0';
std::cout<<ss<<" "<<"\n";
return;
}
else
{
char * s = num[p[k]];

for( int j =0 ; j<strlen(s) ; j++ )
{
char ch = s[j];
*b = ch;
b++;
printallperm1(p,q,b,l,k+1,ss);
b--;
}

}
}

after initializing out and num, call foll fn with current = 0.

void Print(int current, char out[], int num[]){
static int flag = 0;//for not printing the first 8 recursions
if(current==8) flag =1;
if((current >= 9)||(num[current]==1 or 0))
return;
int num_chars;//No. of characters for a digit

if(num[current]==9)
{ num_chars = 4; }
else
{ num_chars = 3; }

for(int j=0; j<=num_chars; j++){
out[current] = getChar(num[current], j);
if(flag){ puts(out); }//print the string
Print(current+1, out, num);
}

}

char getChar(int num, int position){
switch(num){
case 2: switch(position){
case 1: return 'a';
case 2: return 'b';
case 3: return 'c';
}
case 3:________

//upto 9;
}

}

Not sure what the question means, can we push the keys as many times as possible?