Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Generating all possible permutation of a given range

    • 0
    • 1
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 1.01k
    Comment on it

    If you want to generate permutation of the elements in a range in lexicographic order, then next_permutation function defined in STL algorithm might be helpful for you.

    Default template for next_permutation

    template <class InputIterator>
      bool next_permutation (InputIterator first, InputIterator last);
    

    About parameters
    InputIterator first
    InputIterator first for the initial position of the range which is included in the range.
    InputIterator last
    InputIterator last for the final position which it not included in the range.

    A sample program to generate all permutations

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int main()
    {
            string s;
            cout << "Enter the string : ";
            cin >> s;
            sort(s.begin(),s.end()); //we have to sort before to generate all permutations
    
            //Printing all the permutation of a range
            cout << "Permutations of the above string " << endl;
            do {
                    cout << s << endl;
            }
            while (next_permutation(s.begin(),s.end()));
            return 0;
    }
    

    Output of the above program

    Enter the string : abcd
    Permutations of the above string
    abcd
    abdc
    acbd
    acdb
    adbc
    adcb
    bacd
    badc
    bcad
    bcda
    bdac
    bdca
    cabd
    cadb
    cbad
    cbda
    cdab
    cdba
    dabc
    dacb
    dbac
    dbca
    dcab
    dcba
    

    Time complexity for next_permutation is up to linear in half the distance in the range.

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: