The next lexicographic permutation algorithm, also called Pandita’s algorithm, mutates a permutation in place to produce the immediately following dictionary-ordered arrangement. It supports duplicate elements and returns false when the input is already in reverse order, so no larger permutation exists. section 6.2.1
For a mutable sequence, the transformation proceeds as follows:
- Scan from the right to find the first element smaller than the element immediately to its right. section 6.2.1
- If no such element exists, the sequence is reverse-ordered; return false. section 6.2.1
- Find the rightmost element larger than the pivot, swap the two, and reverse the suffix after the pivot. section 6.2.1
- To enumerate every permutation, begin with the sequence in alphabetical order and repeatedly call NextLexiPermutation until it returns false. section 6.2.1
From COATS to COSAT
In COATS, A is the rightmost element immediately followed by something larger. S is the rightmost element larger than A. Swapping them produces COSTA; reversing the suffix TA produces COSAT, the next permutation. Continuing yields COSTA, COTAS, COTSA, and later arrangements. section 6.2.1
