C++

How to Use C++ next_permutation() Function

Permutation is defined as all possible ways in which a number of elements can be arranged. Mathematically, permutation is denoted by N! symbol. A simpler way to calculate the permutation is to multiply all the integers in a descending order from a given number up to unity. Consider 4! case. It will be evaluated as 4!=4.3.2.1=24. We get 24 ways to arrange items with 4 numbers. This article describes using the next_permutation() function in C++.

next_permutation() Function

In C++, permutation is calculated by next_permutation() function. The program will display all possible ways in which given elements can be arranged. Additionally, a user can also define limits of permutation using the range [first, last] in syntax of the program.

How to use next_permutation() function

The function is called in C++ using next_permutation(bidirectional first, bidirectional last) with the parameters in brackets defining the limits of the permutation function. The syntax is as below:

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

Parameter

Bidirectional first: The first element position in the permutation is entered at bidirectional first.

Bidirectional last: The last element position in the permutation is entered at bidirectional last.

Return Value

The function returns true if elements could be arranged in lexicographical order of permutation.
The function returns false if elements could not be arranged in lexicographic order of permutation.

The term lexicographical order means the alphabetical order or dictionary order. In other words, letters or numbers will be arranged from A-to-Z order or from 1 to higher values. Therefore, the smallest number shall come first. An example of lexicographic order for two words; abd or bcd will be from abd then bcd. It is because a word with the alphabet ‘a’ shall come before a word with alphabet ‘b’.

Example 1: Demonstration of Permutation of 4! with range (arr, arr+4)

This program includes an ‘algorithm’ as a header file to call the permutation function. Permutation of four number; {1,2,3,4} has been calculated in below program:

#include <algorithm>
#include <iostream>
using namespace std;
 
int main()
{
    int arr[] = { 1, 2, 3, 4 };
 
    sort(arr, arr + 4);
 
    cout << "The 4! possible permutations with 4 elements:\n";
    do {
        cout << arr[0] << " " << arr[1] << " " << arr[2] << " " << arr[3]<< "\n";
    } while (next_permutation(arr, arr + 4));
 
   
    return 0;
}

An array of four numbers has been defined with a range of {arr, arr+4}, it employs the start point shall be 1st number or unity while last point shall terminate at +4. This program provides 24
possible combinations of four numbers {1,2,3,4} conforming with 4!=4.3.2.1=24 ways.

Example 2: Demonstration of Permutation of 4! with range (arr, arr+3)

This program includes an ‘algorithm’ as header file to call the permutation function just like the previous example. Permutation of four number; {1,2,3,4} has been calculated but 1st point, and last points have been changed to (arr, arr+3) in below program:

#include <algorithm>
#include <iostream>
using namespace std;
 
int main()
{
    int arr[] = { 1, 2, 3, 4 };
 
    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));
 
   
    return 0;
}

An array of four numbers has been defined with a range of {arr, arr+3}, it shows the start point shall be 1st number or unity while last point shall terminate at +3. This program provides six possible combinations of four numbers {1,2,3,4} conforming with 3!=3.2.1=6.

Example 3: Demonstration of Permutation of 4! With range (arr, arr+2)

This program includes an ‘algorithm’ as header file to call the permutation function, just like the previous examples. Permutation of four number; {1,2,3,4} has been calculated but 1st point, and last points have been changed to (arr, arr+2) in below program:

#include <algorithm>
#include <iostream>
using namespace std;
 
int main()
{
    int arr[] = { 1, 2, 3, 4 };
 
    sort(arr, arr + 2);
 
    cout << "The 2! possible permutations with 3 elements:\n";
    do {
        cout << arr[0] << " " << arr[1] <<   "\n";
    } while (next_permutation(arr, arr + 2));
 
   
    return 0;
}

An array of two numbers has been defined with a range of {arr, arr+2}, it shows the start point shall be 1st number or unity while last point shall terminate at +2. This program provides three possible combinations of four numbers {1,2,3,4} conforming with 2!=2.1=2.

Example 4: Demonstration of Permutation for String of Four Alphabets

This program includes ‘algorithm’ and ‘string’ as header files to call the permutation function. Permutation of four alphabetical string; {x,y,z} has been calculated in below program:

#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

 int main()
{
string s = "abcd";
sort(s.begin(), s.end());

do
{ cout << s << '\n'; }
 
while(next_permutation(s.begin(), s.end()));

 return 0;
}

An array of four alphabets has been defined with all the possible combinations range mentioned as s.begin(), s.end(). It employs that range has not been limited. This program provides all possible twenty-four combinations of four alphabets {a,b,c,d} conforming with 4!=4.3.2.1=24 ways.

Conclusion

The next_permutation() function is used to calculate the number of all possible ways in which given elements can be arranged. The next_permutation() function works exactly as using the N! for mathematical evaluation of permutations.

About the author

Anwar Mustafa

I am a technical content writer with a master's degree in electrical engineering. With a unique blend of engineering expertise and exceptional writing skills, I craft engaging and informative content.