Question

Write the routines with the following declarations: void permute( const string & str ); void permute( const string & str, int low, int high ); The first routine is a driver that calls the second and prints all the permutations of the characters in string str. If str is "abc", then the strings that are output are abc, acb, bac, bca, cab, and cba. Use recursion for the second routine.

Answer 1

Answer:

Here is the first routine:

void permute( const string &str ) {  // function with one parameter

 int low = 0;

 int high = str.length();

 permute(str, low, high);

}    

Or you can directly call it as:

 permute(str, 0, str.length());

Explanation:

The second routine:

void permute( const string &str, int low, int high)  

//function with three parameters

{ string str1 = str;

 if ( low == high ) {  //base case when last index is reached

   for (int i = 0; i <= high; ++i)

     cout << str1[i]; }  //print the strings  

 else {

   for (int i=low; i<high; ++i) {  // if base case is not reached

     string temp = str1;   //fix a character

     swap( str1[i], str1[low] ); //swap the values

     permute( str1, low + 1, high );  //calling recursive function (recursion case)

     swap( str1[i], str1[low] );     }  } } //swap again to go to previous position

In this function the following steps are implemented:

A character is fixed in the first position.

Rest of the characters are swapped with first character.

Now call the function which recursively repeats this for the rest of the characters.

Swap again to go to previous position, call the recursive function again and continue this process to get all permutations and stop when base condition is reached i.e. last index is reached such that high==low which means both the high and low indices are equal.

You can write a main() function to execute these functions.

int main() {

 string str;

 cout << "Enter a string: ";

 cin >> str;

 permute(str);  }