Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 225 ยท Arrays and Lists

Next Permutation and Lexicographic Order

Learn the next permutation algorithm in Python: find the pivot, swap, reverse the suffix, then generate all permutations in order, rank and unrank them.

Imagine the digits 1 3 5 4 2. What is the very next number you can make with the same digits, in dictionary order? The answer is 1 4 2 3 5. There is an elegant, in-place algorithm that finds it in O(n) time and O(1) extra memory, and that is the next permutation algorithm. It appears in interview questions, in C++'s std::next_permutation and in countless "generate all arrangements" tasks.

This lesson uses ideas from arrays, two pointers (the reversal step) and array operations. It also pairs naturally with the recursive approach in subsets and permutations: recursion builds permutations by choices, while next-permutation moves from one to the next without recursion or extra storage.

Lexicographic order

Lexicographic order is dictionary order. Compare two sequences element by element from the left; the first position where they differ decides which is smaller. For the elements [1, 2, 3] the six permutations in order are:

TEXT
[1, 2, 3] < [1, 3, 2] < [2, 1, 3] < [2, 3, 1] < [3, 1, 2] < [3, 2, 1]

The first permutation is the sorted (ascending) one and the last is the descending one. "Next permutation" asks: given one of these, produce its successor; if it is the last one, wrap around to the first.

The algorithm in three steps

Take [1, 3, 5, 4, 2].

  1. Find the pivot: scan from the right to find the first index i where a[i] < a[i + 1]. Everything to the right of i is in descending order, so it is already the largest arrangement of those elements; nothing there can be bumped up. Here i = 1 (value 3), because 5, 4, 2 is descending.
  2. Swap with the next larger value: scan from the right again to find the first element greater than a[i] and swap them. The suffix is descending, so the first one from the right that beats 3 is the smallest such value: 4. After swapping: [1, 4, 5, 3, 2].
  3. Reverse the suffix after position i. The suffix is still descending, and we want the smallest arrangement after the new pivot, which is ascending. Reversing turns 5, 3, 2 into 2, 3, 5: [1, 4, 2, 3, 5].

If no pivot exists in step 1, the whole array is descending: it is the last permutation, so reverse everything to get the first.

flowchart LR
    A["1 3 5 4 2"] -->|"pivot = 3<br/>(first drop from the right)"| B["1 3 5 4 2"]
    B -->|"swap pivot with<br/>smallest larger: 4"| C["1 4 5 3 2"]
    C -->|"reverse suffix<br/>5 3 2 becomes 2 3 5"| D["1 4 2 3 5"]

The three steps turn 13542 into 14235 without any extra array.

Python Next permutation in place

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the comparisons use >= in the pivot search and <= in the swap search. That is what makes duplicates work: equal neighbours are not a "drop", and equal values are never chosen as the swap target.

Why it is correct

The suffix after the pivot is the longest descending run at the end. A descending run cannot be increased by rearranging its own elements, so to get a larger permutation we must change something to its left, and the rightmost position we can increase is the pivot. We want the smallest increase, so the pivot receives the smallest larger value from the suffix. After the swap, the suffix is still descending (we replaced one element by a smaller one that was only just larger than the old pivot), so reversing gives the smallest possible tail. Every other permutation between the old and new one would have to share a longer prefix, and none exists.

The cost is O(n): each of the three scans is linear and each position is visited a constant number of times.

Generating all permutations in order

Start from the sorted array and keep calling next_permutation until it wraps. Because of the >= rules, multiset permutations come out without duplicates automatically.

Python All permutations, including duplicates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The total cost is O(n x number of permutations); each step is O(n) worst case but amortized O(1) comparisons, because most steps only touch the last few elements.

The previous permutation

Flip the comparisons: find the first position from the right where a[i] > a[i + 1], swap with the largest element to its right that is smaller, then reverse the suffix. Libraries such as C++ offer prev_permutation for this. If you only need it once, an easy trick is to negate or reverse the ordering of the values and reuse next_permutation.

Ranking and unranking permutations

The k-th permutation of 1..n (0-based) can be built directly with the factorial number system. There are (n-1)! permutations that start with each possible first element, so k // (n-1)! tells you which of the remaining elements goes first; the remainder selects the rest.

Python The k-th permutation and the rank of a permutation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This is O(n^2) with a list, or O(n log n) with a Fenwick tree for the "how many unused smaller elements" count. It answers questions like "what is the millionth permutation?" without generating the first 999,999.

Common applications

  • Next greater number with the same digits: apply the algorithm to the digits of the number (and check for overflow).
  • Iterating over every ordering when n is small (e.g. brute-forcing a route over 8 cities).
  • Permutation ranking, as in the previous section.
  • Next lexicographic string or the next arrangement of a word.

The in-place property is the point: no recursion stack, no list of all permutations, and the sequence is produced one element at a time, which makes it suitable for lazy iteration.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the next permutation of [1, 2, 3]?

    The pivot is 2 (a[1] < a[2]); swapping with 3 gives [1, 3, 2], and reversing the one-element suffix changes nothing.
  2. 2. What should next_permutation do for [3, 2, 1], the last permutation?

    No pivot exists because the array is fully descending. Reversing it produces the smallest permutation, the sorted one.
  3. 3. Why is the suffix reversed in the last step?

    After the swap the suffix is still descending. We want the smallest possible tail after the bumped pivot, which is the ascending order, so reversing does it in O(n).
  4. 4. What is the time and extra space of next_permutation on an array of length n?

    Three linear scans and an in-place swap and reversal: linear time and constant extra memory.

Summary

  • Lexicographic order is dictionary order; the first permutation is ascending, the last is descending.
  • Next permutation: find the rightmost a[i] < a[i+1], swap a[i] with the smallest larger value to its right, reverse the suffix. O(n) time, O(1) space.
  • With >= / <= comparisons it handles duplicates and enumerates each multiset permutation once.
  • If there is no pivot, the array wraps to the first permutation.
  • The factorial number system gives the k-th permutation and the rank of a permutation without enumeration.

Next: Strings in DSA, where the sequence is made of characters and immutability changes the rules.