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

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.


This is a companion discussion topic for the original entry at http://iq.opengenus.org/generating-all-permutations-of-an-array-using-cpp-stl/