Next permutation

Build the next permutation in dictionary order in place: find the first dip from the end, one swap and one reversal.

Order the permutations like words in a dictionary: 123, 132, 213, 231, 312, 321. The next permutation is made with the smallest possible change at the end of the array:

Read the full explanation ↓

Time: O(n)
Space: O(1)
Johnsonbaugh, chapter 6
Grimaldi, chapter 1

Input:

n=5PDF export

The next permutation of 1 3 5 4 2 in dictionary order is 1 4 2 3 5.

def next_permutation(a):
i = len(a) - 2
while i >= 0:
if a[i] < a[i + 1]:
break
i = i - 1
if i < 0:
a.reverse()
return a
j = len(a) - 1
while True:
if a[j] > a[i]:
break
j = j - 1
a[i], a[j] = a[j], a[i]
a[i + 1:] = reversed(a[i + 1:])
return a

Invariant: The part a[i+1..] is decreasing, so every permutation starting with a[0..i] has been used up.

Start

Local variables

Orange = changed in this step

`a` list

13542

Call stack

next_permutation()line 1

Step 1 of 22

How the work grows with input size

Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

comparisons
current input (n=5)

Show as a table

n	comparisons
4	2.5
6	3.5
8	3.9
10	3.1
12	2.8

Explanation

The idea

Order the permutations like words in a dictionary: 123, 132, 213, 231, 312, 321. The next permutation is made with the smallest possible change at the end of the array:

Walk back from the end to the first i with a[i] < a[i + 1] (the first "dip"). Everything after i is decreasing, so no other permutation is left for this prefix.
From the end, find the smallest item larger than a[i] (a[j]) and swap them.
Reverse the tail a[i+1..] so it becomes increasing (its smallest order).

If there is no dip, the array is the last permutation; reversing it all gives the first.

Cost

O(n) per permutation. Repeated from a sorted array, it produces all n! permutations without repeats, even with repeated items.

What to watch in the trace

The i arrow is where the dip is, and j is the item it is swapped with.