Generating all permutations of an array in C++ using STL

Reading time: 20 minutes

For a given array, generate all possible permutations of the array. Given an array of N elements, there will be N! permutations provided all N elements are unique. C++ provides a function in Standard Template Library to accomplish this

Algorithm using C++ STL

We can generate all permutations of an array by making use of the STL function next_permutation. A call of next_permutation returns the next lexicographically smallest permutation. If the sequence is lexicographically largest, the function returns false.

Syntax:

// a is an array
next_permutation(a.begin(), a.end())

Note:

• It will modify the array passed (a in the above example)
• It will generate a is the smallest lexicographic permutation of a that is larger than a
• It will return false in a is the largest permutation possible otherwise it will return true

The steps involved can be described as follows:

1. Sort the array to get lexicographically smallest sequence.
2. Print the array.
3. Generate the next lexicographically smallest sequence.

Implementation

#include <bits/stdc++.h>

using namespace std;

//Display elements of the array
void display(vector<int> a, int n){
    for(int i=0;i<n;i++) cout << a[i] << " ";
    cout << endl;
}

int main()
{
    //Obtaining length of array
    int n;
    cin >> n;

    //Declaring a vector of integers
    vector<int> a(n);
    
    //Taking input of array of integers
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    do{
        //Display the current permutation
        display(a, n);
    }while(next_permutation(a.begin(), a.end())); //Generate next permutation till it is not lexicographically largest

    return 0;
}

Example

//Console input
5
1 2 3 4 5
//Console output
1 2 3 4 5 
1 2 3 5 4 
1 2 4 3 5 
1 2 4 5 3 
1 2 5 3 4 
1 2 5 4 3 
1 3 2 4 5 
1 3 2 5 4 
1 3 4 2 5 
1 3 4 5 2 
1 3 5 2 4 
1 3 5 4 2 
1 4 2 3 5 
1 4 2 5 3 
1 4 3 2 5 
1 4 3 5 2 
1 4 5 2 3 
1 4 5 3 2 
1 5 2 3 4 
1 5 2 4 3 
1 5 3 2 4 
1 5 3 4 2 
1 5 4 2 3 
1 5 4 3 2 
2 1 3 4 5 
2 1 3 5 4 
2 1 4 3 5 
2 1 4 5 3 
2 1 5 3 4 
2 1 5 4 3 
2 3 1 4 5 
2 3 1 5 4 
2 3 4 1 5 
2 3 4 5 1 
2 3 5 1 4 
2 3 5 4 1 
2 4 1 3 5 
2 4 1 5 3 
2 4 3 1 5 
2 4 3 5 1 
2 4 5 1 3 
2 4 5 3 1 
2 5 1 3 4 
2 5 1 4 3 
2 5 3 1 4 
2 5 3 4 1 
2 5 4 1 3 
2 5 4 3 1 
3 1 2 4 5 
3 1 2 5 4 
3 1 4 2 5 
3 1 4 5 2 
3 1 5 2 4 
3 1 5 4 2 
3 2 1 4 5 
3 2 1 5 4 
3 2 4 1 5 
3 2 4 5 1 
3 2 5 1 4 
3 2 5 4 1 
3 4 1 2 5 
3 4 1 5 2 
3 4 2 1 5 
3 4 2 5 1 
3 4 5 1 2 
3 4 5 2 1 
3 5 1 2 4 
3 5 1 4 2 
3 5 2 1 4 
3 5 2 4 1 
3 5 4 1 2 
3 5 4 2 1 
4 1 2 3 5 
4 1 2 5 3 
4 1 3 2 5 
4 1 3 5 2 
4 1 5 2 3 
4 1 5 3 2 
4 2 1 3 5 
4 2 1 5 3 
4 2 3 1 5 
4 2 3 5 1 
4 2 5 1 3 
4 2 5 3 1 
4 3 1 2 5 
4 3 1 5 2 
4 3 2 1 5 
4 3 2 5 1 
4 3 5 1 2 
4 3 5 2 1 
4 5 1 2 3 
4 5 1 3 2 
4 5 2 1 3 
4 5 2 3 1 
4 5 3 1 2 
4 5 3 2 1 
5 1 2 3 4 
5 1 2 4 3 
5 1 3 2 4 
5 1 3 4 2 
5 1 4 2 3 
5 1 4 3 2 
5 2 1 3 4 
5 2 1 4 3 
5 2 3 1 4 
5 2 3 4 1 
5 2 4 1 3 
5 2 4 3 1 
5 3 1 2 4 
5 3 1 4 2 
5 3 2 1 4 
5 3 2 4 1 
5 3 4 1 2 
5 3 4 2 1 
5 4 1 2 3 
5 4 1 3 2 
5 4 2 1 3 
5 4 2 3 1 
5 4 3 1 2 
5 4 3 2 1

Complexity

The next_permutation call is "Up to linear in half the distance between first and last (in terms of actual swaps)."

Note

This method always generates all permutations in the lexicographic order.