Implement C++ full permutation of a given string using STL-C++-php.cn

Implement C++ full permutation of a given string using STL

王林

Release： 2023-09-01 23:33:06

forward

812 people have browsed it

Implement C++ full permutation of a given string using STL

When the characters of a given string are rearranged in any form, an arrangement of the string is formed. For example, in this tutorial, we will discuss how to print all permutations of a given string using C’s standard template library

Input : s = &ldquo;ADT&rdquo;

Output : &ldquo;ADT&rdquo;, &ldquo;ATD&rdquo;, &ldquo;DAT&rdquo;, &ldquo;DTA&rdquo;, &ldquo;TAD&rdquo;, &ldquo;TDA&rdquo;

Explanation : In the given output as you can see all the string are made up of same three character present in our string and are just rearranged thus they fit in the definition of a permutation of a string now there is one more thing to note these are all the permutations possible of string s.

Copy after login

There are two ways to print all permutations of a given string

Rotate()

The first method we are going to use is using the rotation method. In this method, we will use STL's rotate function, which is used to rotate strings, and we will use recursion to print the arrangement.

Example

C code for the above method

#include<bits/stdc++.h>
using namespace std;
void permutations(string s, string ans){
    if(s.size() == 0) {
// when our string which needs to
//be rotated becomes empty then it means
//that our permutation is stored in ans
        cout << ans << "\n";
        return ;
    }
    for(int i = 0; i < s.size(); i++){
        permutations(s.substr(1), ans + s[0]);
        // we are adding the
        // first character in our ans
        // passing all elements from index 1 in our
        // rotate string for next function.
        rotate(s.begin(), s.begin()+1, s.end());
        //rotating such that our second element becomes first
    }
}
int main(){
    string s = "ADT"; // given string
    permutations(s, "");
    return 0;
}

Copy after login

Output

ADT
ATD
DTA
DAT
TAD
TDA

Copy after login

Next_Permutation

Now we will use Another function of STL, next_Permutation, as the name suggests, the return value of this function is whether the next permutation of the string exists. If not, returns false.

As you know, this function checks the next permutation; therefore, we first need to sort the string lexicographically in order to get all possible permutations.

Example

C code for the above method

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s = "ADT"; // given string
    sort(s.begin(), s.end()); // sorting the string
    do{
        cout << s << "\n"; // printing the permutations
    }while(next_permutation(s.begin(), s.end())); // till next_permutations returns false
    return 0;
}

Copy after login

Output

ADT
ATD
DAT
DTA
TAD
TDA

Copy after login

In the above program, we perform a string Sorting, then with the help of next_permutation function, we print all possible permutations.

Conclusion

In this tutorial, we printed all possible permutations of a given string with the help of STL in C. We also learned the C program for the problem and some basic STL functions and their usage. We hope you found this tutorial helpful.

The above is the detailed content of Implement C++ full permutation of a given string using STL. For more information, please follow other related articles on the PHP Chinese website!