Finding lexicographically next permutation C++

Problem Statement

Given array of integers, rearrange the array such that, it becomes lexicographically next greater permutation of numbers i.e. if all the permutations are sorted according to their lexicographical order, then next permutation C++ of the given array is permutation next to the given array in that sorted list of permutations. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

Next Permutation C++ Solutions

Brute Force

Algorithm

1. Find every permutation possible for list of given numbers in array
2. Get the just next larger permutation than the given array arrangement.

Implementation

// Next Permutation C++ Solutions: Brute Force

#include <iostream>

#include <vector>

#include <set>

using namespace std;

bool flag = false;
set < vector < int >> allPermutationList;

// Function to get all permutations using backtracking
void permute(vector < int > & A, int l, int r) {
  if (l == r) {
    allPermutationList.insert(A);

  } else {
    for (int i = l; i <= r; i++) {
      swap(A[l], A[i]);
      permute(A, l + 1, r);
      if (flag) break;
      swap(A[i], A[l]);
    }
  }
}

// Next Permutation C++ Function
vector < int > nextPermutation(vector < int > nums) {
  vector < int > old = nums;

  //Get all permutations
  permute(nums, 0, nums.size() - 1);

  int j = 0;
  // iterate through list to get next permutation
  for (auto i: allPermutationList) {
    // Till the given array is found
    if (i == old) {
      break;
    }
    j++;
  }
  j = j == allPermutationList.size() - 1 ? 0 : j + 1;
  nums = * next(allPermutationList.begin(), j);
  return nums;
}

Complexity

• Time complexity : O(n!)O(n!). Total possible permutations is n!n!.
• Space complexity : O(n)O(n). Since an array will be used to store the permutations.

Next Permutation C++ Built In Library

Algorithm

C++ provide built in function called next_permutation() which rearranges the object as a lexicographically greater permutation. This function returns true if next greater permutation is possible else returns false to indicate that the arrangement is not greater than the previous, but the lowest possible (sorted in ascending order).

Implementation

// Next Permutation C++ Solutions: Next Permutation C++ Built In Library
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
    }

Efficient Approach

Algorithm

1. Find the largest index k such that nums[k] < nums[k + 1]. If no such index exists, just reverse the array nums and return.
2. Find the largest index l such that l > k and nums[k] < nums[l].
3. Swap nums[k] and nums[l].
4. Reverse the sub-array from index k+l to last (nums[k + 1:]).

Implementation

// Next Permutation C++ Solutions:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector < int > nextPermutation(vector < int > nums) {
  int n = nums.size(), k, l;

// Find largest index such that nums[k] < nums[k + 1]
  for (k = n - 2; k >= 0; k--) {
    if (nums[k] < nums[k + 1]) {
      break;
    }
  }

// If nothing found reverse the array and return
  if (k < 0) {
    reverse(nums.begin(), nums.end());
  } else {

// Find larger element than nums[k] from right
    for (l = n - 1; l > k; l--) {
      if (nums[l] > nums[k]) {
        break;
      }
    }
    swap(nums[k], nums[l]);
    reverse(nums.begin() + k + 1, nums.end());
  }
  return nums;
}

Complexity

• Time complexity : O(n).
• Space complexity : O(1).

Conclusion

In this article we discussed various algorithms to find next permutation c++ from brute force to most effective algorithm.

Checkout Minimum Window Substring problem With Detailed Solution here

Got a question or just want to chat? Comment below or drop by our forums, where a bunch of the friendliest people you’ll ever run into will be happy to help you out!