Leetcode 31: Next permutation

A few observations need to be made to solve this problem efficiently. The best way to make those observations is to write out a bunch of sequences (I used most of 1,2,3,4). Notice that we need to look for a pair of decreasing numbers going from right to left. The left of that pair will be the left number of our swap. Now we need to arrange the remaining numbers in descending order from right to left. We can shortcut that by inserting the number we are replacing such that the sequence is ascending from right to left, so then we can just reverse that sequence. The right number to swap will be where we have the smallest number that is bigger than the left number. Once the swap is done, we then reverse numbers after the left number. If all the numbers are ascending from right to left then we are at the last sequence and to get back to the first sequence we reverse all the numbers. Beware of duplicate numbers, which need skipped over in some of the if statements.

So it turns out this algorithm was first discovered a long time ago. According to Knuth (in The Art Of Computer Programming 7.2.1.2), it goes back to the 18th century. This is a nice writeup of the algorithm:
https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
There’s also a nice video discussing this here:
https://www.youtube.com/watch?v=quAS1iydq7U

Here is my c++ source code for the solution: