Next permutation: rearrange an array into the next lexicographically greater order, in place. Walk through the algorithm.

29.1.7 · L3 · Interview

Reported at: Meta

Predict first

What does the in-place algorithm give for these inputs?

func nextPermutation(_ a: inout [Int]) {
    var i = a.count - 2
    while i >= 0 && a[i] >= a[i + 1] { i -= 1 }      // last position that can still grow
    if i >= 0 {
        var j = a.count - 1
        while a[j] <= a[i] { j -= 1 }                // smallest larger value to its right
        a.swapAt(i, j)
    }
    a[(i + 1)...].reverse()                           // the suffix is descending; make it the smallest
}
for start in [[1, 2, 3], [3, 2, 1], [1, 1, 5], [1, 3, 2], [2]] {
    var a = start
    nextPermutation(&a)
    print(start, "->", a)
}
  • [1, 2, 3] -> [1, 3, 2] / [3, 2, 1] -> [1, 2, 3] / [1, 1, 5] -> [1, 5, 1] / [1, 3, 2] -> [2, 1, 3] / [2] -> [2]
  • [3, 2, 1] stays [3, 2, 1]
  • [1, 3, 2] -> [3, 1, 2]

Mental model. An odometer: the last wheel that can still turn up does, and every wheel to its right resets to its smallest value.

Three steps, O(n) time and O(1) memory. (1) Scan from the right for the first position i where a[i] < a[i+1]; everything to its right is in descending order, so it is already the largest arrangement of that tail. (2) If there is such an i, find the smallest value to its right that is larger than a[i] (scan from the right, because the tail is descending) and swap the two. (3) Reverse the tail after position i: it is still descending after the swap, so reversing gives the smallest arrangement and therefore the very next permutation. If no such i exists the array was the last permutation, and step 3 on the whole array wraps around to the first.

Check it on small cases, which the program does: [1,2,3] becomes [1,3,2], [3,2,1] wraps to [1,2,3], [1,1,5] becomes [1,5,1] (use >= in step 1 so duplicates are handled), and a single element is unchanged. In Swift, a[(i + 1)...].reverse() reverses a slice in place, and swapAt avoids copying. Mention that the standard library has no nextPermutation, so you write it. Reported at Meta (anonymous, unverified).

It bumps the last growable position with the next larger value and then resets the tail to ascending; the last permutation wraps to the first.

Common traps

  • Using > instead of >= in the scan, which loops or goes wrong with duplicate values.
  • Sorting the tail instead of reversing it. It works but costs O(n log n) when O(n) is possible.

They might follow up with

  • How would you get the previous permutation? Mirror the steps: find the first descent from the right in the other direction.
  • How many permutations does it step through? n! for distinct values; fewer with duplicates.

Related questions

  • 29.1.8 When do you use a sliding window, and how do the fixed-size and variable-size versions differ?
  • 29.1.5 Given a string with brackets, remove the fewest parentheses to make it valid. How do you count them, and how…
  • 29.1.1 Two-sum: given an array and a target, return the indices of two elements that add up to it. How do you get…

← Can a string be built by concatenating words from a list (words may…   When do you use a sliding window, and how do the fixed-size and… →