Generate all permutations of a string that follow given constraints

Given a string, generate all permutations of it that do not contain ‘B’ after ‘A’, i.e., the string should not contain “AB” as a substring.

Examples:

Input : str = “ABC”
Output : ACB, BAC, BCA, CBA
Out of 6 permutations of “ABC”, 4 follow the given constraint and 2 (“ABC” and “CAB”) do not follow.

Input : str = “BCD”
Output : BCD, BDC, CDB, CBD, DCB, DBC

A simple solution is to generate all permutations. For every permutation, check if it follows the given constraint.

#include

using namespace std;

  

void permute(string& str, int l, int r)

{

  

    

    

    if (l == r) {

        if (str.find("AB") == string::npos)

            cout << str << " ";

        return;

    }

  

    

    for (int i = l; i <= r; i++) {

        swap(str[l], str[i]);

        permute(str, l + 1, r);

        swap(str[l], str[i]);

    }

}

  

int main()

{

    string str = "ABC";

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

    return 0;

}

The above solution first generates all permutations, then for every permutation it checks if it follows given constraint or not.

NewPermutation

An efficient solution is to use Backtracking. We cut down the recursion tree whenever we see that substring “AB” is formed. How do we do this? we add a isSafe() function. Before doing a swap, we check if previous character is ‘A’ and current character is ‘B’.

#include

using namespace std;

  

bool isSafe(string &str, int l, int i, int r)

{

    

    

    

    if (l != 0 && str[l-1] == 'A' && str[i] == 'B')

       return false;

  

    

    

    

    if (r == l+1 && str[i] == 'A' && str[l] == 'B')

      return false;

  

   return true;

}

  

void permute(string& str, int l, int r)

{

    

    

    if (l == r) {

        cout << str << " ";

        return;

    }

      

    

    for (int i = l; i <= r; i++) {

  

      

      

      if (isSafe(str, l, i, r)) {

        swap(str[l], str[i]);

        permute(str, l + 1, r);

        swap(str[l], str[i]);

      }

    }

}

  

int main()

{

    string str = "ABC";

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

    return 0;

}



If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the "Improve Article" button below.

Article Tags :


1

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.




Source link

Write a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.