[Leetcode Solution] Next Permutation

Analysis 

Let's consider a simpler situation. Given n integers [1..n] and a permutation generated by these n integers. How to find the next permutation.

It seems easy right. If we treat the permutation as a integer number, our purpose is to increase value of this number to the nearest one by reorder the integers.

Say the permutation is like this [a(1),a(2),...,a(n)]. if i<j and a(i) < a(j). If we swap ai and aj the value of permutation will increase. In order to get the nearest bigger number, we would like to increase a bit in least significant bit by swap it with a bit at more least significant direction. So the solution is find the first a(i) that there is an a(j) that a(i) < a(j) and i<j. After that we swap the value of a(i) and a(j) then resort the integers from a(i+1) to a(n) in order to change it to the smallest one.

Now consider the given scenario. There are different integers in the permutation and duplicates.

• First we can just treat different integers as the sequence of 1 .. n because they share the same order. Only order makes a difference rather then the value.
• Second if duplicates exist, we will only update the part which finds the first a(i).

Note

Code