std::next_permutation and prev_permutation in C++

It is used to rearrange the elements in the range [first, last) into the next lexicographically greater permutation. A permutation is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range). Different permutations can be ordered according to how they compare lexicographically to each other.

Syntax:

template 
bool next_permutation (BidirectionalIterator first,
                       BidirectionalIterator last);
Parameters: 
first, last : Bidirectional iterators to the initial
and final positions of the sequence. The range 
used is [first, last), which contains all the elements 
between first and last, including the element pointed 
by first but not the element pointed by last.

return value: 
true : if the function could rearrange 
the object as a lexicographicaly greater permutation.
Otherwise, the function returns false to indicate that 
the arrangementis not greater than the previous, 
but the lowest possible (sorted in ascending order).

Application : next_permutation is to find next lexicographicaly greater value for given array of values.
Examples:

Input : next permutation of 1 2 3 is 
Output : 1 3 2

Input : next permutation of 4 6 8 is 
Output : 4 8 6
// C++ program to illustrate
// next_permutation example
// this header file contains next_permutation function
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
    int arr[] = { 1, 2, 3 };
    sort(arr, arr + 3);
    cout << "The 3! possible permutations with 3 elements:\n";
    do {
        cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n";
    } while (next_permutation(arr, arr + 3));
    cout << "After loop: " << arr[0] << ' '
         << arr[1] << ' ' << arr[2] << '\n';
    return 0;
}

Output:

The 3! possible permutations with 3 elements:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
After loop: 1 2 3

std::prev_permutation

It is used to rearranges the elements in the range [first, last) into the previous lexicographically-ordered permutation. A permutation is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range). Different permutations can be ordered according to how they compare lexicographicaly to each other.

Syntax :

template 
bool prev_permutation (BidirectionalIterator first,
                         BidirectionalIterator last );
parameters: 
first, last : Bidirectional iterators to the initial
and final positions of the sequence. The range 
used is [first, last), which contains all the
elements between first and last, including 
the element pointed by first but not the element
pointed by last.

return value: 
true : if the function could rearrange 
the object as a lexicographicaly smaller permutation.
Otherwise, the function returns false to indicate that 
the arrangement is not less than the previous, 
but the largest possible (sorted in descending order).

Application : prev_permutation is to find previous lexicographicaly smaller value for given array of values.
Examples:

Input : prev permutation of 3 2 1 is 
Output : 3 1 2 

Input : prev permutation of 8 6 4 is 
Output :8 4 6
// C++ program to illustrate
// prev_permutation example
// this header file contains prev_permutation function
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
    int arr[] = { 1, 2, 3 };
    sort(arr, arr + 3);
    reverse(arr, arr + 3);
    cout << "The 3! possible permutations with 3 elements:\n";
    do {
        cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n";
    } while (prev_permutation(arr, arr + 3));
    cout << "After loop: " << arr[0] << ' ' << arr[1]
         << ' ' << arr[2] << '\n';
    return 0;
}

Output:

The 3! possible permutations with 3 elements:
3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3
After loop: 3 2 1


Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/stdnext_permutation-prev_permutation-c/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

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

Skip to toolbar