next_permutation and prev_permutation in C++ with examples

In this tutorial, we will learn about C++ STL functions next_permuation and prev_permutation. We will also understand it more using examples.

Permutation is a different possible arrangement from a set of elements that can be obtained by changing the order of its element. If N is the number of elements then there could be N! arrangements that can be obtained.

std::next_permutation() in C++

This comes under the Standard Template Library of C++. It rearranges the elements such that we can get lexicographically the next permutation which will be greater than this ordered pair. The range of arrangement will be [first_element, last_element).

Syntax: next_permutation(first_iterator , last_iterator);

The function will return true only if it will be able to rearrange a set of elements which will be lexicographically the next element that will be greater than this ordered pair. If it will give a set of elements that is the smallest of all the arrangements then this function will return false.

Example code 1 :

#include<bits/stdc++.h>
using namespace std;

// main function
int main() {
   vector<int> v = {1,2,3,4,5};
   // prev_permuation function
   next_permutation(v.begin(),v.end());
   for(auto &p : v) {
      cout<<p<<" ";
   }
   cout<<endl;
   return 0;
}
Output: 1 2 3 5 4

Example code 2:

#include<bits/stdc++.h>
using namespace std;

//main function
int main() {
    vector<int> v = {1,2,3};
    do {
        for(auto &p : v) {
         cout<<p<<" ";
        }
        cout<<endl;
      } while(next_permutation(v.begin(),v.end()));
   return 0;
}
Output: 1 2 3
        1 3 2 
        2 1 3 
        2 3 1 
        3 1 2 
        3 2 1

Internal working of this function:

  1. Start traversing elements from the last and find the first element which does not follow the decreasing order sequence. Let it be x.
  2. Now find the smallest greater element on the right part of x and let’s keep it y.
  3. Swap x and y elements.
  4. Reverse the subsequence after the next position of y. Hence by following all this we will get our required result.

std::prev_permutation()

This also comes under the Standard Template Library of C++. It rearranges the elements such that we can get lexicographically the previous permutation which will be smaller than this ordered pair. The range of arrangements will be [first_element, last_element).

Syntax:  prev_permutation(first_iterator, last_iterator);

This function will return true only if it will be able to rearrange its element lexicographically such that we can get the previous permutation which will be smaller than this ordered pair. If it will rearrange the elements that will be highest of all the possible ordered pairs then this will return false.

Example code 1:

#include<bits/stdc++.h>
using namespace std;
 
//main function
int main() {
   vector<int> v = {1,2,3,5,4};
   // prev_permutation function
   prev_permutation(v.begin(),v.end());
   for(auto &p : v) {
       cout<<p<<" ";
   }
   cout<<endl;
   return 0;
}
Output: 1 2 3 4 5

Example code 2:

#include<bits/stdc++.h>
using namespace std;

//main function
int main() {
   vector<int> v = {3,2,1};
   do {
      for(auto &p : v) {
          cout<<p<<" ";
      }
      cout<<endl;
   } while(prev_permutation(v.begin(),v.end()));
   return 0;
}

Output: 3 2 1 
        3 1 2 
        2 3 1 
        2 1 3 
        1 3 2 
        1 2 3

Internal working of this function:

  1. Start traversing from the last and find the first element that does not follow the increasing order sequence. Let it be x.
  2. Now we need to find the largest element on the right side of x that is smaller than x. Let it be y.
  3. Swap x and y elements.
  4. Reverse the elements after the new position of y.

 

Leave a Reply

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