**Problem:**

Please find the problem here.

**Analysis:**

The next permutation is lexicographically larger than the current permutation, therefore, if a sequence is monotonic decreasing, there is no way we can have a next permutation, in this case, we simply reverse the permutation, that gives a monotonically increasing sequence, which is the 1st permutation.

If the sequence is not monotonically decreasing, there must be a increase in value. In particular, there must an increase that is least significant.

Look at this example, we have:

6, 3, 5, 4, 2, 1

The least significant increase happens here.

6,

__, 4, 2, 1__

**3, 5**Here is where we can try to increase it minimally lexicographically. 3 can be minimally increase to 4, so it becomes this:

6, 4, X, X, X, X

We do not know the 'X' yet, but because we wanted to increase it minimally, so it only make sense if we order the rest monotonically increasing like this:

6, 4, 1, 2, 3, 5

**So that would be our answer, notice because the original 4 numbers are monotonically decreasing, to obtain this monotonic increasing sequence, we do not need to sort, all we have to do is to reverse it.**

**Solution:**

The algorithm is as follow:

- Scan the sequence from the back to find the last strictly increasing tuple (a[i] > a[i + 1])
- If there is none, reverse the whole sequence, this is the case where the sequence is monotonically decreasing, no next permutation, so return the first one.
- If there is one, search forward to find the
**last**element a[j] that is strictly minimally larger than a[i]. (i.e a[j] > a[i], a[j] <= a[k] for all k in [i + 1, n), j maximal if multiple j exists) - Swap a[i] and a[j] (Here we increase the sequence minimally lexicographically)
- Reverse a[i + 1] to a[n - 1] (Here we made the remaining list monotonically increasing)
- Return;

Note the bold

**last**above. This is an important detail. Swapping a[i] and a[j] will generally make the sequence smaller, therefore we need to make sure we find the last one to replace to ensure monotonicity (so that step 5 is valid).

**Code:**

#include "stdafx.h" // https://leetcode.com/problems/next-permutation/ #include "LEET_NEXT_PERMUTATION.h" #include <map> #include <iostream> #include <sstream> #include <vector> #include <string> using namespace std; namespace _LEET_NEXT_PERMUTATION { class Solution { public: void nextPermutation(vector<int>& nums) { if (nums.size() < 2) { return; } int i = nums.size() - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } int s; if (i == -1) { // This is a monotonically decreasing sequence! s = 0; } else { s = i + 1; // nums[i] < nums[i + 1] for (int j = i + 2; j < nums.size(); j++) { // Finding the last occurrence of the least number larger than nums[i] // and swap with it to ensure the suffix is still monotonically decreasing if (nums[j] > nums[i] && nums[j] <= nums[s]) { s = j; } } int temp = nums[s]; nums[s] = nums[i]; nums[i] = temp; s = i + 1; } int t = nums.size() - 1; while (s < t) { int temp = nums[s]; nums[s] = nums[t]; nums[t] = temp; s++; t--; } } }; }; using namespace _LEET_NEXT_PERMUTATION; int LEET_NEXT_PERMUTATION() { Solution solution; int input_array[5] = { 2, 3, 1, 3, 3 }; vector<int> input(input_array, input_array + 5); solution.nextPermutation(input); for (int i = 0; i < 5; i++) { cout << input[i] << ", "; } return 0; }

## No comments :

## Post a Comment