Monday, October 31, 2016

LeetCode OJ - Next Permutation

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, 3, 5, 4, 2, 1

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:


  1. Scan the sequence from the back to find the last strictly increasing tuple (a[i] > a[i + 1])
  2. 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.
  3. 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)
  4. Swap a[i] and a[j] (Here we increase the sequence minimally lexicographically)
  5. Reverse a[i + 1] to a[n - 1] (Here we made the remaining list monotonically increasing)
  6. 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