Previous Permutation
Given an array of digits, you are required to find out its previous permutation.
Example:
Input:
{2, 1, 3}
Output:
{1, 3, 2}
Solution
This problem can be translated into two sections:
 find the suffix subarray which is in ascending order, and the number before this subarray is arr[i]. This indirectly means that subarray starting with arr[i] is the smallest sequence in all the subarrays that starts with arr[i];
 within the ascending subarray, search from backwards the first number arr[j] that is smaller than the number arr[i];
Due to the two searching operations above, we made sure that if we swap arr[i] and arr[j] then there are two facts:
 the ascending subarray is still in ascending order  arr[j] is the first number that is smaller than arr[i] which means the numbers after arr[j] should be all bigger while the numbers before arr[j] are all smaller;
 the subarray started with arr[j] is smaller than that started with arr[i] now  since arr[i] is bigger than arr[j];
So if reverse the subarray after arr[j] now then the subarray will be in descending order which means itâ€™s the biggest subarray that starts with arr[j].
As a result, the previous biggest array should be the adjacent previous permutation while the current is the smallest that starts with arr[i].
Note
 Still there is a special case which should be handled exceptionally: if the current sequence is already the smallest then the previous permutation should be biggest sequence or just remain the same? Depend on the requirements.
 Actually the ascending and descending order mentioned above can also be translated into nondescending or nonascending order, which is more feasible in different situations.


Always welcome new ideas and practical
tricks, just leave them in the comments!