Compute the next permutation

Problem statement

Write a function that takes an array of numbers (eq. a permutation) and returns the next permutation using dictionary ordering rules.

However, if the permutation is the last permutation under the dictionary ordering, your function should return the empty array.

EXAMPLE:

  Input: p = [6,2,1,5,4,3,0]

  Output: [6,2,3,0,1,4,5]

Solution

Here is the actual code of the algorithm that implements a solution to compute the next permutation of the given sequence:

func next(p: [Int]) -> [Int] {
    // Evaluate boundaries of the suffix
    let x = edgeOfSuffix(s: p), y = p.count - 1 
    // Seems no more permutations left, hence the empty result
    if x == -1 { return [] }
    // Prepare state of the algorithm
    var perm = p
    // Find the next smallest entry after `x` in the suffix
    // and swap it with the entry in `x` position
    swapNextInSuffix(s: &perm, x: x)
    // Build the smallest suffix possible by sorting it from 
    // the smallest to the largest using reverse - since suffix
    // elements are ordered from the largest to the smallest
    reverse(seq: &perm, x + 1, y)
    // Here is the answer
    return perm
}

Following is the traditional section with assertions to validate the code performs as advertised and establish a baseline for any improvement work in the future:

Compute the next permutation test assertions

Bits & pieces

This coding challenge took mutiple iterations to get the code working correctly with edge cases and then it took a few more attempts to factor it out so that the code is readable and far easier to understand. Refactoring effort helped a lot to highlight important parts of the algorithm and turn it into something that is far more easier to read, comprehend and reason about.

Lets get started!

The first statement evaluates boundaries of the suffix (eq. sequence of numbers in ascending order) to perform the manipulations on, since that is the way to compute the next permutation under dictionary order:

// Evaluate boundaries of the suffix
let x = edgeOfSuffix(s: p), y = p.count - 1

As you have noticed, the statement above uses edgeOfSuffix helper function and below you can find its code. However, it’s worth to explain how does it work to help aid better understanding of the algorithm’s inner workings.

The current step of the algorithm evaluates boundaries of the suffix and finds out its edge, eq. first occurence where an entry on the left is less than an entry on the right:

Find an edge of the suffix

Finding the edge of the suffix is the purpose of this helper function and the result will be very useful later during find and exchange step of computing the next permutation:

public func edgeOfSuffix(s: [Int]) -> Int {
    // Put reading head `x` into the position next to the last
    // in the sequence, therefore subtract 2 from the count.
    var x = s.count - 2
    // Enumerate pairs of elements, eq. [x] and [x + 1] 
    while x >= 0 {
        // Look for a pair of elements where x < y, eq. 1 < 5
        if s[x] < s[x + 1] { break }
        // Move on to the next pair of elements
        x -= 1
    }
    // Here is the edge of the suffix or -1 if the edge is not found
    return max(x, -1)
}

Following statement will return an empty array as a result, since edge search result that equals -1 indicates the given sequence is either empty or represents the last permutation of the sequence:

// Seems no more permutations left, hence the empty result
if x == -1 { return [] }

This statement makes a local writeable copy of p argument into perm variable. so that the following steps of the algorithm will be able to make changes to the sequence during find and exchange and suffix transformation steps:

// Prepare state of the algorithm
var perm = p

Next statement is find and exchange step computes the first part of the next permutation using an in-place exchange of the suffix edge discovered earlier and an entry within the suffix that is the next smallest entry after the suffix edge’s entry:

// Find the next smallest entry after `x` in the suffix
// and swap it with the entry in `x` position
swapNextInSuffix(s: &perm, x: x)

Now, lets take a look at the internals of swapNextInSuffix helper function to better understand why it is useful in this case and how does it work.

Here is a picture outlining mechanics of the current step, eq. find the next smallest entry (starting from the end of sequence) after entry in position x and exchange the two:

Find and exchange items to get first part of the next permutation

Finding the next smallest entry after x and exchanging the two entries using in-place swap technique is the purpose of this helper function:

public func swapNextInSuffix(s: inout [Int], x: Int) {
    // Prepare state of the algorithm
    let lhs = s[x], y = s.count - 1
    // Enumerate sequence's suffix elements in reverse order,
    // eq. from n...0
    for i in (x...y).reversed() {
        // Skip entries smaller than or equal to the entry of `x`
        if lhs >= s[i] { continue }
        // Swap entry of `x` with the entry of `i`, eq. it would be
        // the first entry of `i` greater than entry of `x`
        swap(&s, x, i)
        // Break out from the loop, we're done
        break
    }
}

As soon as the exchange step is completed, the remaining part of the algorithm is suffix transform step that re-arranges elements of the suffix in reverse order (eq. from smallest to largest/left-to-right):

Suffix transformation step

Since elements of the suffix (if any) at this point are in descending order (eq. from largest to smallest/left-to-right) the code simply needs to apply reverse function to the part of the original sequence denoted by (x + 1) ... y range:

// Build the smallest suffix possible by sorting it from 
// the smallest to the largest using reverse - since suffix
// elements are ordered from the largest to the smallest
reverse(seq: &perm, x + 1, y)

After elements of the suffix are in reverse order, our function is ready to return an answer representing the next permutation of the original sequence:

// Here is the answer
return perm

That’s all folks! 🎰

Here is a Swift playground for this article at Github: Compute the next permutation.