Introduction

When dealing with permutations of a sequence, one might often need to find the next permutation that is lexicographically greater than the given one. In simpler terms, given a permutation, the task is to rearrange it into the numerically next larger permutation, if possible. If no such permutation exists (i.e., the given permutation is the greatest possible), then it wraps around to the smallest permutation.

Technical Explanation

The algorithm to find the next greater permutation of a given string or sequence can be understood through a series of systematic steps:

1. Identify the Pivot:
   Find the largest index k such that the character at index k is less than the character at index k+1. If no such index exists, this means the sequence is sorted in descending order, and hence, we return the smallest permutation (i.e., reverse the entire sequence).
2. Find the Successor to Pivot:
   Next, identify the largest index l greater than k such that the character at index k is less than the character at index l.
3. Swap Characters:
   Swap the characters at indices k and l. This step ensures that the permutation remains greater but close to the original permutation.
4. Reverse Subsequence:
   Finally, reverse the sequence from k+1 to the end of the sequence. This step ensures that we get the smallest permutation possible for the rearranged suffix, thereby maintaining the next greater permutation.

Demonstration with an Example

Consider the string "534976":

• Step 1: Find the pivot. The largest index k where the character is smaller than the next character is at index 3 with value 4 (since 9 > 4).
• Step 2: Find the successor. The largest index l greater than k where sequence[k] < sequence[l] is index 5 with value 6.
• Step 3: Swap the characters at indices 3 and 5. The sequence becomes "536974".
• Step 4: Reverse the subsequence from k+1 (index 4) till the end. The sequence becomes "536479".

Hence, the next permutation is "536479".

Algorithm in Pseudocode

The following pseudocode demonstrates the structure of this algorithm:

• Edge Case - Descending Order Sequence:
• Identity:
• Lexicographical Order: