VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.15 of 16 in this moduleFree

Next Permutation

Rearrange numbers into the next larger ordering in place: from listing all n! permutations, to the O(n) pivot, swap and reverse rule derived from first principles. Then duplicates, the previous permutation, the k-th permutation and enumerating search spaces.

about 10 min 4 Python examples 2 quick checks

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).

text
[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.

python
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

the six permutations of 1, 2, 3 in order, each with its decreasing suffix and pivot marked; 3 2 1 has no pivot and wraps around to 1 2 3; listing all n! permutations is hopeless for n = 20.
Diagram— the six permutations of 1, 2, 3 in order, each with its decreasing suffix and pivot marked; 3 2 1 has no pivot and wraps around to 1 2 3; listing all n! permutations is hopeless for n = 20.

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:

  1. 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.
  2. The pivot is the value just before that suffix (here 3 at 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.
  3. 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.
for [1, 3, 5, 4, 2], the decreasing suffix 5, 4, 2 is found, the pivot is 3, it is swapped with 4 to give [1, 4, 5, 3, 2], and the suffix is reversed to give [1, 4, 2, 3, 5].
Diagram— for [1, 3, 5, 4, 2], the decreasing suffix 5, 4, 2 is found, the pivot is 3, it is swapped with 4 to give [1, 4, 5, 3, 2], and the suffix is reversed to give [1, 4, 2, 3, 5].
python
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?

  1. Reversing is a style choice
  2. The suffix is still in decreasing order after the swap, so reversing makes it increasing (its smallest order) in O(n) without a sort
  3. Sorting would give the wrong answer
  4. To handle duplicates
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)!.

python
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.

python
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?

  1. Use the factorial number system: each leading choice covers (n − 1)! permutations, so pick items by dividing k by factorials
  2. Call next_permutation 10¹⁸ times
  3. Generate all permutations and index into the list
  4. It's impossible
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

  1. Why is a decreasing suffix already "maxed out"?
  2. How is the pivot defined?
  3. Why swap with the rightmost larger value?
  4. Why is reversing the suffix enough, instead of sorting it?
  5. What happens when there's no pivot?
  6. How do you find the k-th permutation without stepping k times?
Answers
  1. A decreasing sequence is its own largest arrangement; no reordering of it alone is larger.
  2. The first position from the right whose value is smaller than its right neighbour.
  3. The suffix is decreasing, so the rightmost value larger than the pivot is the smallest such value: the smallest possible increase.
  4. After the swap the suffix is still decreasing, so reversing it gives increasing order in O(n).
  5. The array is the largest permutation; reversing it all gives the smallest (wrap-around).
  6. Factorial number system: each first choice covers (n − 1)! permutations, so divide k by factorials to choose each position.