Given an array or string, the task is to find the next lexicographically greater permutation of it in Java.
Examples:
Input: string = "gfg"
Output: ggf
Input: arr[] = {1, 2, 3}
Output: {1, 3, 2}
In C++, there is a specific function that saves us from a lot of code. It’s in the header file #include<algorithm>. The function is next_permutation(a.begin(), a.end()). It is used to rearrange the elements in the range [first, last) into the next lexicographically greater permutation. A permutation is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range). Different permutations can be ordered according to how they compare lexicographically to each other.
Apparently, Java does not provide any such inbuilt method. Therefore, this article discusses how to implement the next permutation function in Java along with its algorithm.
Naïve Approach: Generate all the possible permutations of the given number/string, store them in a list and then traverse it to find the just greater permutation of the given number.
Time Complexity= O(n!*n) : n! to generate all the permutations and an extra n to traverse and find the just greater permutation.
Space Complexity = O(n!) : to store all the permutations.
This approach is very naive and complex to implement. suppose we have array size as 100, which is not very big, but, it will generate 100! permutations. which is a huge number. Moreover, we will have to need 100! space to store all of them and then traverse it to find the next greater permutation.
Algorithm:
INTUITION BEHIND THIS APPROACH: Suppose we have 13542 as our question and we have to find its next permutation, on observing it is clear that when we traverse from the last we see that the numbers are increasing up till and 5 and 3 is the first index which breaks the increasing order, hence, the first step:
- Find the longest non-increasing suffix and find the pivot (3 i.e., index 1 is the pivot).
- If the suffix is the whole array, then there is no higher order permutation for the data (In this case do as the question asks, either return -1 or the sorted array).
- Find the rightmost successor to the pivot : to find the rightmost successor again start traversing from the back, the moment we encounter an element greater than the pivot we stop as it is the required element (here it is 4 index=3). This works because as we are traversing from the back, the elements are linearly increasing up till 3(this is the first time array starts decreasing) so, the moment we encounter an element greater than 3 it is indeed the just greater element or successor of 3 and all the elements to the left of 4 (till 3) are greater than 3 and all the elements to the right of 4 are smaller than 3.
- Swap the successor and the pivot.
- Reverse the suffix: once we swap the successor and pivot, a higher place value is modified and updated with a greater value, so it must be clear that we will obtain the next greater permutation only if the elements after the pivot are arranged in increasing order .
Below is the implementation of the above approach:
Java
// Java program to implement// the next_permutation methodimport java.util.Arrays;public class nextPermutation { // Function to swap the data // present in the left and right indices public static int[] swap(int data[], int left, int right) { // Swap the data int temp = data[left]; data[left] = data[right]; data[right] = temp; // Return the updated array return data; } // Function to reverse the sub-array // starting from left to the right // both inclusive public static int[] reverse(int data[], int left, int right) { // Reverse the sub-array while (left < right) { int temp = data[left]; data[left++] = data[right]; data[right--] = temp; } // Return the updated array return data; } // Function to find the next permutation // of the given integer array public static boolean findNextPermutation(int data[]) { // If the given dataset is empty // or contains only one element // next_permutation is not possible if (data.length <= 1) return false; int last = data.length - 2; // find the longest non-increasing suffix // and find the pivot while (last >= 0) { if (data[last] < data[last + 1]) { break; } last--; } // If there is no increasing pair // there is no higher order permutation if (last < 0) return false; int nextGreater = data.length - 1; // Find the rightmost successor to the pivot for (int i = data.length - 1; i > last; i--) { if (data[i] > data[last]) { nextGreater = i; break; } } // Swap the successor and the pivot data = swap(data, nextGreater, last); // Reverse the suffix data = reverse(data, last + 1, data.length - 1); // Return true as the next_permutation is done return true; } // Driver Code public static void main(String args[]) { int data[] = { 1, 2, 3 }; if (!findNextPermutation(data)) System.out.println("There is no higher" + " order permutation " + "for the given data."); else { System.out.println(Arrays.toString(data)); } }} |
[1, 3, 2]
Time Complexity: O(n)
Auxiliary Space: O(1)
