Permutations

Rubik’s Cube

Generating Permutations is an interesting problem that helps you to think about the two most important algorithm concepts: recursion and backtracking.

Recursion:

Recursion is one of the techniques that is useful if you can divide the problem into multiple sub-parts and solve them independently.

There are two ways to solve the problem recursively. You can either build the solution incrementally with every recursive call [Algorithm1] where the base case becomes your solution or build the solution based on the result from the recursive call [Algorithm2] by adding up solutions from solving sub-parts of the problem.

Algorithm 1:

The result holds the incremental solution and with every recursive call, we add one more character to the result.

void permute(string result, string remStr)
{
 if(remStr.length()==0) {
   cout << result << endl;
   return;
 }
 
 int n = remStr.length();
 
 for(int i=0;i<n;i++)
 {
   char c = remStr[i];
   string temp = remStr.substr(0,i)+remStr.substr(i+1,n-i);
   permute(c+result, temp);
 }
}

Algorithm 2:

Another recursive algorithm is where we build a partial solution and then use it to complete the main solution.

Permutation of s(n) is equal to permutation of s(n-1) and inserting nth character in every position for each permutation of s(n-1).

vector <string> permute2(string str)
 {
   vector<string> result;
  
   if(str.length() == 1)
   {
     result.push_back(str);
     return result;
   }
 
   vector<string> out = permute2(str.substr(1));
 
   char ch = str[0];
 
   for(int i=0;i<out.size();i++)
   {
     string temp = out[i];
     for(int j=0;j<=temp.length();j++)
     {
       string newStr = temp.substr(0,j) + ch + temp.substr(j);
       result.push_back(newStr);
     }
   }
   return result;
 }

Backtracking:

Backtracking is a technique where you branch out in one direction to build a solution and then backtrack to the origin point to move into another direction.

In this algorithm before each recursive call, you swap the subsequent characters. After the recursive call, you revert the swap and move to the next set of subsequent characters.

void permute3(string str, int i, int len)
{
  if(i==len-1)
  {
    cout << str << endl;
    return;
  }
 
  for(int j=i;j<len;j++)
  {
    swap(str[i], str[j]);
    permute3(str, i+1, len);
    swap(str[i], str[j]);
  }
}