Lexicographical order basically means dictionary order. A sequence is said to be lexicographically larger than another sequence, if it'll appear later in a dictionary. Eg, the following list is lexicographically sorted -
ABC, ACB, BAC, BCA, CAB, CBA
Now, consider a sequence
int a[] = {1,5,3,8,7,5,4,2};
By some trail and error, we can conclude that lexicographically the next sequence is {1,5,4,2,3,5,7,8}. Now how we go about generating it algorithmically?
Intuitively, to “increase” the sequence as little as possible, we need to take the same approach as when counting up numbers. We need to modify the rightmost elements(analogous to units digits) and disturb the letters on the left as little as possible. For example, if we swap the first two elements we get {2,5,3,8,7,5,4,1}, which is much larger lexicographically when compared to what we get if we swap the two rightmost elements {1,5,3,8,7,5,2,4}. Now the question is, which numbers do we swap and why?
Let's identify the longest weakly increasing suffix (each element larger than or equal to the elements on their right). In the given scenario, such sequence is {8,7,5,4,2}. The critical observation here is to note that this sequence is already lexicographically sorted in decreasing order. It is another way to saying that it is not possible to make a number larger than 87542 using the digits 2,4,5,7,8. Note that to increase the given sequence as little as possible, we need to increase the prefix (everything apart from the weakly increasing sub-sequence) and the suffix as little as possible.
Let us consider the element immediately to the left of this sub sequence. In our case, it is 3. The second critical observation is to note that this element has to be by definition lesser than the leftmost element of the weakly increasing sub-sequence. We can therefore conclude that this element is lesser than atleast one element in the sub-sequence {8,7,5,4,2}. To minimize the prefix, we swap this element with the smallest element in the suffix that is larger than 3.
Old sequence
New sequence
Finally, to minimize the suffix, we sort it in increasing order, to get {1,5,4,2,3,5,7,8}. Note that we just need to reverse it to sort it in increasing order.
And there we have it! The next lexicographic permutation is {1,5,4,2,3,5,7,8}. Once again, the steps are
1. Identify the longest weakly increasing suffix.
2. If the suffix is the entire sequence, then the sequence is already reverse sorted lexicographically and it is not possible to generate a larger sequence.
3. Else, identify the element immediately to the left of the suffix.
4. Swap this element with the smallest element in the suffix larger than it to minimize the prefix.
5. Sort the new suffix in increasing order to minimize the suffix.
6. Done!
package test; public class NextLargest { public static char[] getNextPermutation(char[] seq){ char curPerm[] = seq; int i=curPerm.length-1,j=curPerm.length-1; while(i>0 && curPerm[i]<=curPerm[i-1]) i--; if(i==0) return null; while(curPerm[j]<=curPerm[i-1]) j--; char temp = curPerm[i-1]; curPerm[i-1] = curPerm[j]; curPerm[j] = temp; j=curPerm.length-1; while(i<j){ temp = curPerm[i]; curPerm[i] = curPerm[j]; curPerm[j] = temp; i++;j--; } return curPerm; } public static void main(String[] args) { char ch[] = {'1','5','3','8','7','5','4','2'}; System.out.println(getNextPermutation(ch)); } }Algorithm 12 Amazon 12 Google 12
COMMENTS