Sunday, 14 December 2014

Permutations and Combinations of a String, A Recursion Solution

PROBLEM: 
Implement a routine that prints all possible orderings of the characters in a string. In other words, print all permutations that use all the characters from the original string. For example, given the string “hat", your function should print the strings "tha", "aht", "tah", "ath", "hta", and "hat". Treat each character in the input string as a distinct character, even if it is repeated. Given the string "aaa", your routine should print "aaa" six times. You may print the permutations in any order you choose.

SOLUTION:





vector<string>& permutate(const string& str, const PERMUTATION& kind, const string& in_probs, string form, int id)
{
       static vector<string> remuts;
       static int callingTimes = 0;
       callingTimes++;
       if (id >= str.length())
              return remuts;

       string probs = form.length() <= 0 ? str : in_probs;
       for (int x = 0; x < probs.length(); x++)
       {
              string nform = form + probs[x];
              if (nform.length() == str.length() || kind == COMBINATIONS_NO_ORDER)
              {
                     //Display new ocurance
                     remuts.push_back(nform);
                     cout << nform << endl;
              }
              if (kind == NORMAL_OCCURANCES)
              {
                     //OUTPUT: has same str length regardless of characters order, avoiding redundant of the same character in single ocurance (e.g.: "aat" of "hat" is wrong)
                     //remove Xth-char from the new prob string to get all next occurances
                     string nprobs = probs.substr(0, x) + probs.substr(x + 1, probs.length() - (x + 1));
                     if (nprobs.length() > 0 && id + 1<str.length())
                           permutate(str, kind, nprobs, nform, id + 1);//non-repeated occurances
              }
              else if (kind == COMBINATIONS_NO_ORDER)
              {
                     //OUTPUT: has deferent lengths, deferent characters orders not allowed, avoiding redundant of the same character in single ocurance (e.g.: "aat" of "hat" is wrong and "at" with "ta" is wrong)
                     //remove [0,1, .. ,Xth_char] from new prob string to prevent simillar-reordered combinations
                     string nprobs = probs.substr(x + 1, probs.length() - (x + 1));
                     if (nprobs.length() > 0 && id + 1<str.length())
                           permutate(str,kind, nprobs, nform, id + 1);//non-repeated occurances
              }else if (kind == TRUTH_TABLE)
              {
                     //OUTPUT: has same str length regardless of characters order, allow redundant of the same character in single ocurance (e.g.: "aaa" of "hat" is correct)
                     //use the same set of charaters in the new passed prob to allow output looks liks truth table.
                     permutate(str, kind, probs, nform, id + 1);//all occurances
              }
       }

       if (form.length() == 0)
              cout << "Permutations:" << remuts.size() << ", callingTimes:" << callingTimes << endl;

       return remuts;
}






Saturday, 13 December 2014

Matrix Tracing


A very clean single function to solve HackerRank's contest that has been explained in V. Anton Spraul vedio.

Problem Statement
A word from the English dictionary is taken and arranged as a matrix. e.g. "MATHEMATICS"
MATHE 
ATHEM 
THEMA 
HEMAT 
EMATI 
MATIC 
ATICS
There are many ways to trace this matrix in a way that helps you construct this word. You start tracing the matrix from the top-left position and at each iteration, you either move RIGHT or DOWN, and ultimately reach the bottom-right of the matrix. It is assured that any such tracing generates the same word. How many such tracings can be possible for a given word of length m+n-1 written as a matrix of size m * n? 

Solution:
int trace(int row, int col)
{
static int count = 0;

if (row == 1 && col == 1)
count++;
else
{
if (row <= 0 || col <= 0)
return -1;
trace(row, col - 1);
trace(row - 1, col);
}
return count;
}

Input:
  trace( 4 , 3 );

Output:
  10

Explain:
  Recursive upward traversal as shown in the next figure.