Next Permutation

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.

Brute Force Approach :

Find all possible permutations of the given array.
Print the Next permutation right after the er given input sequence.

Time Complexity: O(N * N!), N represents the number of elements present in the input sequence. represent all possible permutation. Therefore, It takes the time complexity O(N*N!).
Auxiliary Space: O(N), for storing the permutation in some data structure.

Using C++ in-build function:

C++ provides an in-built function called next_permutation(), that return directly lexicographically in the next greater permutation of the input.

C++

#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;
}

Java

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));
    }
}

Python

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)

JavaScript

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