Daily bit(e) of C++ | Next permutation
Daily bit(e) of C++ #240, Common interview problem: Next lexicographical permutation.
Today, we will look at a common interview problem: Next lexicographical permutation.
Given a random-access range of elements that support strict-weak-ordering, return the next lexicographical permutation (with wrap-around).
Your implementation cannot use permutation algorithms.
For example, for the input {1,3,8,4,2}, the next permutation is {1,4,2,3,8}.
Before you continue reading, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/Kh6s54soE.
Solution
Let's consider a number with digits Qabc and ask: Which order of the digits abc will force Q to change when producing the next permutation?
This will happen when the digits abc form the maximum number, i.e., in non-ascending order.
To form the next possible permutation, we want to swap the digit Q with the next higher digit from the digits abc and then reverse this sub-range. For example: 3842 (Q==3, abc == {842}), 4832 (after swap), 4238 (after reverse).
We can apply the same logic to any range. More formally:
find the first out-of-order element from the end of the range (i.e. find Q)
find the first element higher than Q from the end of the range
swap this element with Q
reverse the subrange
If we do not find Q, all elements are already in non-ascending order, forming the lexicographically largest permutation. At this point, we want to wrap around by reversing the entire range.
