Next greater permutation
Let’s first understand what does permutation mean. Definition taken from Wikipedia says, “In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word “permutation” also refers to the act or process of changing the linear order of an ordered set.”
So, as the definition say, permutation means rearranging a set of given objects in all the possible orders. As we can see in the above diagram, three different colors can be arranged in 6 ways i.e. {RGB, RBG, GRB, GBR, BRG, BGR}.
A mathematical formula to compute the number of arrangements possible for n different objects is given by n!, where n! = n*(n-1)*(n-2)*…*1
There are many ways to systematically generate all permutations of a given sequence. One classic algorithm is based upon finding the next permutation in lexicographical/dictionary/alphabetical order, if it exists.
So, the problem statement here is, we are given a set of alphabets maybe we can call it a string, and we have to find the next lexicographical set of alphabets or next lexicographical greater string or the string that will come next in the dictionary after the current string having the same set of alphabets as in the current string.
Let’s take an example of numbers to understand better.
Number = [4,5,2,6,7,3,1]
Next greater number will be = [4,5,2,7,1,3,6]
Brute Force
First thing that will come to our mind is, find all the permutations of the given number and the smallest of those permutations which is also greater than our current number will be our answer. As we saw above, there are n! possibilities (n=number of digits in number), considering all the digits as distinct, so if we go on finding all the permutations for a given number, it will take O(n!) time to compute. That’s a heavy time complexity if the n is a large number.
Optimization
We need to think how we can improve on this. If we observe carefully, maybe for a smaller set of numbers, we might see a patterns. Let’s try with a few examples:
[2,1,3] = next greater number is 231
[1,1,5] = next greater number is 151
[2,3,5,4] = next greater number is 2435
[3,2,1] = we can’t form a number greater than the current number from all the possible permutations
Takeaways from the above observation:
Case 1: [3,2,1]
Here we start moving from right end and try to find the first decreasing element, so that we can replace it with the element greater than itself from the right side of it.
Case 2: [2,3,5,4]
This graph proves that on swapping 4 and 5, the sequence starting from 8, i.e. 86432 is still sorted in the non-increasing order and it’s quite obvious as we are replacing the first decreasing element with the element that is just bigger than it and hence maintaining the non-increasing order.
One more observation we can take from here is, while searching the next larger element from index j=i+1 to right, we can stop the search at index j when nums[j] become less than or equal to nums[i], as elements after that index can never be greater than nums[i].
Code Snippet
Complexity Analysis
Time Complexity = O(n){to find first decreasing element in the worst case, e.g. [1,5,4,3,2]} + O(n) {to find the next greater number in the remaining sub array on the right} + O(1) {to swap the first decreasing element with next larger element} + O(n/2) {to reverse the sub array from i+1 to len to sort into ascending order} = O(n)
As no addition space is required, it will take no extra space.
Hence, Space complexity: O(1)
Thanks for devoting your time to this article. I hope you find it helpful and it gives you a clear insight.
If you still have any query, feel free to respond. If you find it helpful, then please share it among your colleagues. Your claps motivate me to write more such blogs! :)
