Problem. Rearrange nums into the next lexicographically larger permutation, in place. If it's already the
largest (fully decreasing), wrap around to the smallest (fully increasing).
[1, 2, 3] → [1, 3, 2]
[1, 3, 5, 4, 2] → [1, 4, 2, 3, 5]
[3, 2, 1] → [1, 2, 3]
ML context. Enumerating orderings shows up in search: trying feature orders, evaluating permutation tests (shuffle labels, recompute a statistic), brute-forcing small assignment problems, or stepping through a hyperparameter grid in a fixed order so a job can resume from where it stopped. "What comes next?" in O(n) and O(1) memory, without storing all n! orderings, is exactly what such iterators need.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| "Next" in what order? | Lexicographic (dictionary) order | Defines the target exactly |
| Already the largest? | Wrap to the smallest | Fully decreasing → reverse |
| Duplicates? | Possible | Must not get stuck or repeat |
| In place, O(1) extra? | Yes | Rules out generating a list |
| n? | Up to 100 | n! is astronomically large |
2. Step 2: Brute force: list every permutation
Generate all permutations in sorted order, find the current one, return the next.
from itertools import permutations
def next_perm_brute(nums):
perms = sorted(set(permutations(nums))) # n! tuples (set handles duplicates)
i = perms.index(tuple(nums))
nums[:] = perms[(i + 1) % len(perms)]
nums = [1, 3, 5, 4, 2]
next_perm_brute(nums)
assert nums == [1, 4, 2, 3, 5]
nums = [3, 2, 1]
next_perm_brute(nums)
assert nums == [1, 2, 3]
print("brute force works for tiny n: O(n! · n log(n!)) time, O(n! · n) space")
At n = 10 that's 3,628,800 permutations; at n = 20, about 2.4 × 10¹⁸. The constraint (n up to 100, O(1) memory) rules this out completely. We need to compute the next one directly.
3. Step 3: Optimise: think about dictionary order
First principles. To get the smallest larger arrangement, change the array as far to the right as possible, and by as little as possible. Reason it out in three steps:
- Find the suffix that can't grow. Scan from the right while values are decreasing. A decreasing suffix (like
5, 4, 2) is already at its largest order: no rearrangement of it alone gives a larger permutation. - The pivot is the value just before that suffix (here
3at index 1), the rightmost position that can grow. Replace it with the smallest value in the suffix that's larger than it (4). Because the suffix is decreasing, that's the rightmost value larger than the pivot. - Make the suffix as small as possible. After the swap the suffix is still decreasing (
5, 3, 2), so reversing it makes it increasing (2, 3, 5), its smallest order.
import random
from itertools import permutations
def next_permutation(nums):
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]: # 1. skip the non-increasing suffix
i -= 1
if i >= 0: # 2. a pivot exists
j = len(nums) - 1
while nums[j] <= nums[i]: # rightmost value larger than the pivot
j -= 1
nums[i], nums[j] = nums[j], nums[i]
lo, hi = i + 1, len(nums) - 1 # 3. reverse the suffix (all of it if no pivot)
while lo < hi:
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
def brute(nums):
perms = sorted(set(permutations(nums)))
return list(perms[(perms.index(tuple(nums)) + 1) % len(perms)])
for case in ([1, 2, 3], [3, 2, 1], [1, 1, 5], [1, 3, 5, 4, 2], [1], [2, 2, 2]):
got = list(case)
next_permutation(got)
assert got == brute(case), case
rng = random.Random(31)
for _ in range(1000):
case = [rng.randint(0, 3) for _ in range(rng.randint(1, 6))] # duplicates included
got = list(case)
next_permutation(got)
assert got == brute(case)
print("pivot, swap, reverse: O(n) time, O(1) space, matches brute force with duplicates")
- Time: at most three linear scans: O(n). Space: O(1).
- Duplicates: the comparisons
>=and<=(not>and<) skip equal values, so equal neighbours never count as a pivot and the swap always picks a strictly larger value. Using strict comparisons here is the classic bug. - Wrap-around for free: if no pivot exists (
i = −1), step 3 reverses the whole array, turning the largest permutation into the smallest.
Quick check
After swapping the pivot with the rightmost larger value, why reverse the suffix rather than sort it?
Show the answer
B. The suffix is still in decreasing order after the swap, so reversing makes it increasing (its smallest order) in O(n) without a sort — The swap preserves the suffix's decreasing order, so a reversal is enough, and it's O(n) instead of O(n log n).
4. When the constraints change
| If the constraint becomes… | Best approach | Time | Space |
|---|---|---|---|
| Tiny n, any method | List all permutations | O(n! · n) | O(n! · n) |
| Classic, in place | Pivot, swap, reverse | O(n) | O(1) |
| Previous permutation | Mirror: find an increasing suffix, swap with the rightmost smaller value, reverse | O(n) | O(1) |
| Enumerate all, in order | Start sorted, call next n! − 1 times | O(n! · n) total (O(1) amortised per step) | O(1) |
| Jump to the k-th permutation | Factorial number system | O(n²) (O(n log n) with a tree) | O(n) |
| Resume a long enumeration | Store the current permutation; call next | O(n) per step | O(n) |
| Next larger number with the same digits | Same algorithm on the digits | O(d) | O(d) |
Change A: jump straight to the k-th permutation
Calling next k times is O(k · n). Instead, count: with n items, each choice of first item covers (n − 1)!
permutations. So the first item's index is k // (n − 1)!; recurse on the rest with k % (n − 1)!.
from itertools import permutations
from math import factorial
def kth_permutation(items, k):
"""k is 0-based, over the sorted order of distinct items."""
pool = sorted(items)
out = []
for remaining in range(len(pool), 0, -1):
block = factorial(remaining - 1)
idx, k = divmod(k, block)
out.append(pool.pop(idx)) # O(n) pop: O(n²) overall
return out
items = [1, 2, 3, 4]
all_perms = [list(p) for p in permutations(items)] # already in sorted order
for k in range(len(all_perms)):
assert kth_permutation(items, k) == all_perms[k]
assert kth_permutation(list(range(20)), 10**18)[:3] == [8, 4, 3] # 10¹⁸ // 19! = 8, and so on
print("k-th permutation without enumerating: O(n²) even for n = 20, k = 10¹⁸")
For n = 20 and k = 10¹⁸, this answers instantly, while stepping k times would never finish.
Change B: a resumable enumeration (e.g. a search job)
Because next_permutation needs only the current arrangement, a long search can checkpoint just that one array
and resume after a crash, with no list of n! states to store.
def next_permutation(nums):
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i < 0:
return False # wrapped: enumeration finished
j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1:] = reversed(nums[i + 1:])
return True
order = [0, 1, 2]
seen = [order[:]]
checkpoint = None
while next_permutation(order):
seen.append(order[:])
if len(seen) == 3:
checkpoint = order[:] # "crash" here: save one small array
assert len(seen) == 6
resumed = checkpoint[:]
rest = []
while next_permutation(resumed):
rest.append(resumed[:])
assert seen[:3] + rest == seen
print("resumable enumeration: the checkpoint is just the current permutation")
Quick check
You need the 10¹⁸-th permutation of 20 items. What's the right approach?
Show the answer
A. Use the factorial number system: each leading choice covers (n − 1)! permutations, so pick items by dividing k by factorials — Counting blocks of permutations jumps straight to the answer in O(n²), instead of stepping k times.
5. Saying it out loud
"Listing all n! permutations is hopeless. To get the smallest larger arrangement I change as far right and as little as possible: scan from the right past the decreasing suffix, which is already at its largest. The value before it is the pivot; swap it with the rightmost larger value in the suffix, then reverse the suffix to make it as small as possible. O(n) time, O(1) space. If there's no pivot, reversing the whole array wraps to the smallest. I'd use non-strict comparisons so duplicates work."
Check yourself
- Why is a decreasing suffix already "maxed out"?
- How is the pivot defined?
- Why swap with the rightmost larger value?
- Why is reversing the suffix enough, instead of sorting it?
- What happens when there's no pivot?
- How do you find the k-th permutation without stepping k times?
Answers
- A decreasing sequence is its own largest arrangement; no reordering of it alone is larger.
- The first position from the right whose value is smaller than its right neighbour.
- The suffix is decreasing, so the rightmost value larger than the pivot is the smallest such value: the smallest possible increase.
- After the swap the suffix is still decreasing, so reversing it gives increasing order in O(n).
- The array is the largest permutation; reversing it all gives the smallest (wrap-around).
- Factorial number system: each first choice covers (n − 1)! permutations, so divide k by factorials to choose each position.