The C++ Algorithm next_permutation function is employed to rearrange the elements within the range [first, last) into the subsequent lexicographically larger permutation.
A permutation refers to one of the various potential arrangements or orderings in which a set or collection of items can be organized. It is represented by N! where N signifies the total count of elements within the set.
Items are compared by employing the < operator in the initial version, or by utilizing the specified binary comparison function comp in the alternate version.
Syntax
default (1) template <class BidirectionalIterator>
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);
custom (2) template <class BidirectionalIterator, class Compare>
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last,
Compare comp);
Parameter
A bidirectional iterator that indicates the initial element within the range to undergo permutation.
last: An input iterator pointing to the element immediately following the last one in the range to be permuted.
A custom binary predicate function called comp is defined by the user. This function takes two arguments and evaluates to true if the two arguments are in a specific order, otherwise it evaluates to false. The function adheres to the concept of strict weak ordering to arrange the elements accordingly.
Return value
It returns true if the function was able to rearrange the object into a permutation that is lexicographically greater.
Otherwise, the function will return false to signify that the configuration is not larger than the previous one, rather it is the smallest achievable while being sorted in an ascending order.
Complexity
The time complexity ranges up to linear based on half the distance between the first and last elements.
Data Races
The elements within the range [first, last) undergo modification.
Exceptions
This function will raise an exception if either element is exchanged or if an operation on the iterator results in an exception.
Note: The invalid parameters cause an undefined behavior.
Example 1
Let's examine a straightforward example to illustrate the functionality of the next_permutation method:
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
int main()
{
string s = "aba";
sort(s.begin(), s.end());
do {
cout << s << '\n';
} while(next_permutation(s.begin(), s.end()));
return 0;
}
Output:
aab
aba
baa
Example 2
Let's see another simple example:
#include <iostream> // std::cout
#include <algorithm> // std::next_permutation, std::sort
using namespace std;
int main () {
int myints[] = {1,2,3};
sort (myints,myints+3);
cout << "The 3! possible permutations with 3 elements:\n";
do {
cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
} while ( next_permutation(myints,myints+3) );
cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[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
Example 3
Let's see another simple example:
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
template<typename It>
bool next_permutation(It begin, It end)
{
if (begin == end)
return false;
It i = begin;
++i;
if (i == end)
return false;
i = end;
--i;
while (true)
{
It j = i;
--i;
if (*i < *j)
{
It k = end;
while (!(*i < *--k))
/* pass */;
iter_swap(i, k);
reverse(j, end);
return true;
}
if (i == begin)
{
reverse(begin, end);
return false;
}
}
}
int main()
{
vector<int> v = { 1, 2, 3, 4 };
do
{
for (int i = 0; i < 4; i++)
{
cout << v[i] << " ";
}
cout << endl;
}
while (::next_permutation(v.begin(), v.end()));
}
Output:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
Example 4
Let's see a simple example:
#include <iostream>
#include <algorithm>
using namespace std;
// Program to find all lexicographically next permutations
int main()
{
string s = "231";
// Optional: sort the string in natural order before calling
// std::next_permutation inside a loop to print all permutations,
// not just the ones that follows specified string lexicographically
// std::sort(begin(s), end(s));
// find all lexicographically next permutations using
// std::next_permutation
while (1)
{
// print current permutation
cout << s << " ";
// find next permutation in lexicographic order
if (!next_permutation(begin(s), end(s)))
break;
}
return 0;
}
Output:
231 312 321
