Here is an algorithm that generates the next permutation in lexicographic order, changing the given permutation in-place:
- Find the largest index k such that a[k] < a[k+1]. If no such index exists, exit (the permutation is the last permutation).
- Find the largest index l such that a[k] < a[l].
- Swap a[k] with a[l].
- Reverse the sequence from a[k+1] up to and including the final element a[n].
Is the next permutation generated in constant amortized time and if yes, how to verify it?