LeetCode 31 Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1, 2, 3 → 1, 3, 2
3, 2, 1 → 1, 2, 3
1, 1, 5 → 1, 5, 1

Difficulty
Medium

Analysis

Permutation:
A permutation is each one of the N! possible arrangements the elements can take.

Next permutation:
Different permutations can be ordered according to how they compare lexicographicaly to each other; The first such-sorted possible permutation (the one that would compare lexicographically smaller to all other permutations) is the one which has all its elements sorted in ascending order, and the largest has all its elements sorted in descending order.

[7,    8,     6,     9,     8,    7,    2]
                     ^
             A[i]  A[i+1]

[7,    8,     7,     9,     8,    6,    2] Wrong!

[7,    8,     7,     2,     6,    8,    9] Correct!

Take the above example, to get the next permutation, we need to find the common prefix, then choose a least number, that is greater than the begining element of the prefix, from the remaining sequence, replace/swap the begining element of the remaining sequence with that least number, reordering the remaining sequence.

How to find the common prefix?
Starting from the rear of the sequence, find the first element (A[i]) that is in ascending order, by which means A[i] < A[i+1]. them elements in 0 ... i is the common prefix.

Note:
before we reach A[i], the rear part of the sequence is in descending order, so we can use binary search to find the least number that is greater than A[i]. Also, if we found no A[i] < A[i + 1], we swap(i, n - i - 1)

Solutions

1. Cpp solution 9ms

class Solution {
public:
    void nextPermutation(vector<int> &A){
        int n = A.size();
        if(n < 2) return;
        int j = n-2;
        while(j >= 0 && A[j] >= A[j+1]) j--;

        if(j < 0) {
            sort(A.begin(), A.end());
            return;
        } 

        int i = j + 1;
        while(i < n && A[i] > A[j]) i++;
        i--;

        swap(A[i], A[j]);
        sort(A.begin()+j+1, A.end());
    }
};

Note:
C++ standard library provides next_permutation() to get the next permutation.

void nextPermutation(vector<int> &A){
    next_permutation(A.begin(), A.end());
}

1. Go solution 12ms ```go func nextPermutation(nums []int) { i := len(nums) - 1 for ; i >= 0; i-- {

    if i < len(nums)-1 && nums[i] < nums[i+1] {
        idx := binarySearch(nums, i+1, nums[i])
        nums[i], nums[idx] = nums[idx], nums[i]
        sort.Ints(nums[i+1:])
        break
    }
   

   } if i == -1 {

    sort.Ints(nums)
   

   } }

func binarySearch(nums []int, begin, target int) int { low, high := begin, len(nums)-1 for low <= high { mid := low + (high-low)/2 if nums[mid] > target { low = mid + 1 } else { high = mid - 1 } } return high } ``

Reference

https://www.nayuki.io/page/next-lexicographical-permutation-algorithm