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.
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