On this page
Description
Lexicographic rearrangement finds the arrangement that comes right after (or right before) the current one in dictionary order: the next permutation. It works in place and in O(n), without listing all n! arrangements. The algorithm finds the rightmost place where the sequence can still grow, raises it by the smallest possible amount, and puts everything after it in its smallest order.
We'll go from simple to more technical:
- The pattern: find the pivot, swap with its successor, reverse the suffix.
- Where step-by-step enumeration shows up in production.
- The mistakes: the wrong swap partner, and confusing permutations with combinations.
- What it doesn't do: jumping straight to the k-th arrangement.
The approach
You could generate every permutation, sort them and pick the one after the current one. That takes O(n! * n) time and memory for a single step, which is hopeless past a handful of elements. You only need to look at the end of the array instead.
Think of the arrangement as a number, like 13542. To get the next larger one, change it as far to the right as possible. Read from the right while the digits keep rising: 2, 4, 5. That tail, 5 4 2, is already in its largest order, so changing it alone can't help. The first digit that breaks the rise, 3, is the pivot. Raise it by as little as possible, to the smallest digit in the tail that's bigger than it, which is 4. Then put the tail in its smallest order.
| Step | What it finds | Array |
|---|---|---|
| Start | 1 3 5 4 2 | |
| 1. Pivot | from the right, the first value smaller than its right neighbor: 3 | 1 3 5 4 2 |
| 2. Swap | from the right, the first value bigger than 3: 4. Swap them | 1 4 5 3 2 |
| 3. Reverse | the part after the pivot, 5 3 2, becomes 2 3 5 | 1 4 2 3 5 |
So the arrangement after 13542 is 14235.
1. Scan right-to-left for the first index i where nums[i] < nums[i + 1] (the "pivot").
2. If found, scan right-to-left again for the first index j > i where nums[j] > nums[i],
and swap them.
3. Reverse everything after index i - it was in non-increasing order, so reversing makes
it ascending: the smallest possible arrangement of that suffix.
Why reverse instead of sort? After the swap, the tail is still in descending order. Reversing it gives ascending order in O(n). If there's no pivot at all, the array is the last arrangement (fully descending). Reversing the whole array then wraps around to the first one.
Where you'll see it
Test generators that try every ordering of a fixed set use this. So do searches that must stop and resume later. Each step needs only the current arrangement, so nothing else has to be stored, and the order is the same every run.
Which tool for which job?
| You need | Use |
|---|---|
| The next arrangement in dictionary order | next permutation: pivot, swap, reverse |
| The previous arrangement | the mirror: flip every comparison |
| The k-th arrangement directly | the factorial number system |
| Every arrangement, in order, without duplicates | sort, then step with next permutation |
| The next subset of the same size | the next bitmask with the same number of 1s |
| All arrangements, order doesn't matter | backtracking or itertools.permutations |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Swapping with the largest element of the suffix | it skips arrangements | swap with the smallest element bigger than the pivot (first from the right) |
| Sorting the suffix after the swap | correct, but O(n log n) | reverse it - it's already in descending order |
Strict > in the scans with duplicates | the pivot or partner is wrong | >= to find the pivot, <= to find the partner |
| Forgetting the last arrangement | no pivot and nothing happens | reverse the whole array (wrap to the first) |
| Using it for "next subset" | wrong problem | a bitmask or a combination step |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why is the part after the pivot already the largest arrangement of its own values?
Show answer
Every position after the pivot failed the test that would have made it the pivot. So, read from the left, the tail never rises: it's in descending order. Descending order is always the largest arrangement of a set of values.
2. Why swap the pivot with the first bigger value from the right, and not with any bigger value?
Show answer
The tail is in descending order, so the first bigger value from the right is the smallest one that's still bigger than the pivot. Swapping in the smallest possible bigger value gives the very next arrangement, not just a bigger one.
3. What changes to turn next permutation into previous permutation?
Show answer
Every comparison flips. The pivot is the first value from the right that's bigger than its right neighbor. The partner is the largest value in the tail that's still smaller than the pivot. The tail ends up in descending order, its largest arrangement.
Key takeaways
- The pivot is the rightmost position where a bigger arrangement can start. Everything after it is already as large as it can be.
- Swap the pivot with the smallest bigger value in the tail, then reverse the tail.
- With no pivot, the array is the last arrangement. Reversing it wraps to the first.
- Previous permutation is the mirror image: flip every comparison.
- It works because arrangements of a fixed set of values have a total order. It doesn't apply to subsets.