Previous Permutation

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:

  1. find the suffix sub-array which is in ascending order, and the number before this sub-array is arr[i]. This indirectly means that sub-array starting with arr[i] is the smallest sequence in all the sub-arrays that starts with arr[i];
  2. within the ascending sub-array, 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:

  1. the ascending sub-array 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;
  2. the sub-array 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 sub-array after arr[j] now then the sub-array will be in descending order which means it’s the biggest sub-array 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

  1. 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.
  2. Actually the ascending and descending order mentioned above can also be translated into non-descending or non-ascending order, which is more feasible in different situations.
1
2
3
4
5
6
7
8
9
void previousPermutation(vector<int>& arr){
int i = arr.size()-2, j = i+1;
while(i>0 && arr[i] <= arr[i+1]) i--;
while(j>0 && arr[j] >= arr[i]) j--;
if(j == 0) return ;
swap(arr[i++], arr[j]);
j = arr.size()-1;
while(i < j) swap(arr[i++], arr[j--]); //reverse;
}

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