How to use C++ in-build function In Data Structures and Algorithms
C++ provides an in-built function called next_permutation(), that return directly lexicographically in the next greater permutation of the input.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to find the next permutation
void nextPermutation(vector<int>& arr)
{
// Find the first element that is not in decreasing order from right
auto it = is_sorted_until(arr.rbegin(), arr.rend());
// If all elements are in decreasing order, reverse the array
if (it == arr.rend()) {
reverse(arr.begin(), arr.end());
} else {
// Find the next permutation
auto next_it = upper_bound(arr.rbegin(), it, *it);
swap(*it, *next_it);
reverse(arr.rbegin(), it);
}
}
// Driver code
int main()
{
// Given input array
vector<int> arr = { 3, 2, 1 };
// Function call
nextPermutation(arr);
// Printing the answer
for (auto i : arr) {
cout << i << " ";
}
return 0;
}
#include <stdio.h>
// Function to swap two elements in an array
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to reverse elements in an array from start to end
void reverse(int arr[], int start, int end) {
while (start < end) {
swap(&arr[start], &arr[end]);
start++;
end--;
}
}
// Function to find the next lexicographically greater permutation of an array
void nextPermutation(int arr[], int size) {
// Find the first element from the right that is not in decreasing order
int i = size - 2;
while (i >= 0 && arr[i] >= arr[i + 1]) {
i--;
}
// If such an element is found, find the smallest element from the right that is greater than it
if (i >= 0) {
int j = size - 1;
while (arr[j] <= arr[i]) {
j--;
}
// Swap the two elements
swap(&arr[i], &arr[j]);
}
// Reverse the elements from i+1 to the end to get the next permutation
reverse(arr, i + 1, size - 1);
}
// Function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Driver code
int main() {
int arr[] = {3, 2, 1};
int size = sizeof(arr) / sizeof(arr[0]);
// Find the next permutation
nextPermutation(arr, size);
// Print the next permutation
printArray(arr, size);
return 0;
}
import java.util.Arrays;
public class NextPermutation {
public static void nextPermutation(int[] nums) {
// Find the first element from the right that is not in decreasing order
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// If such an element is found, find the smallest element from the right that is greater than it
if (i >= 0) {
int j = nums.length - 1;
while (nums[j] <= nums[i]) {
j--;
}
// Swap the two elements
swap(nums, i, j);
}
// Reverse the elements from i+1 to the end to get the next permutation
reverse(nums, i + 1);
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private static void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
public static void main(String[] args) {
int[] nums = { 3, 2, 1 };
nextPermutation(nums);
System.out.println(Arrays.toString(nums));
}
}
def next_permutation(nums):
# Find the first element from the right that is not in decreasing order
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
# If such an element is found, find the smallest element from the right that is greater than it
if i >= 0:
j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1
# Swap the two elements
nums[i], nums[j] = nums[j], nums[i]
# Reverse the elements from i+1 to the end to get the next permutation
nums[i + 1:] = reversed(nums[i + 1:])
nums = [3, 2, 1]
next_permutation(nums)
print(nums)
using System;
public class Program {
public static void NextPermutation(int[] nums) {
// Find the first element from the right that is not in decreasing order
int i = nums.Length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// If such an element is found, find the smallest element from the right that is greater than it
if (i >= 0) {
int j = nums.Length - 1;
while (nums[j] <= nums[i]) {
j--;
}
// Swap the two elements
Swap(nums, i, j);
}
// Reverse the elements from i+1 to the end to get the next permutation
Reverse(nums, i + 1);
}
private static void Swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private static void Reverse(int[] nums, int start) {
int i = start, j = nums.Length - 1;
while (i < j) {
Swap(nums, i, j);
i++;
j--;
}
}
public static void Main() {
int[] nums = { 3, 2, 1 };
NextPermutation(nums);
Console.WriteLine(string.Join(" ", nums));
}
}
Output
1 2 4 3 5 6
Next Permutation
Given an array arr[] of size N, the task is to print the lexicographically next greater permutation of the given array. If there does not exist any greater permutation, then print the lexicographically smallest permutation of the given array.
Examples:
Input: N = 6, arr = {1, 2, 3, 6, 5, 4}
Output: {1, 2, 4, 3, 5, 6}
Explanation: The next permutation of the given array is {1, 2, 4, 3, 5, 6}.Input: N = 3, arr = {3, 2, 1}
Output: {1, 2, 3}
Explanation: As arr[] is the last permutation.
So, the next permutation is the lowest one.
Let’s first understand what is lexicographical order in the above-given program.
We have to check that the order of the array sequence is greater than the previous array sequence. The output will be just larger sequence of the array.
Contact Us