31. Next Permutation #

Problem #

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:

Input: nums = [1]
Output: [1]

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

Problem Summary #

Implement the function to get the next permutation. The algorithm needs to rearrange the given sequence of numbers into the next greater permutation in lexicographical order. If there is no next greater permutation, rearrange the numbers into the smallest permutation (i.e., sorted in ascending order). The modification must be done in place, and only constant extra space is allowed.

Solution Approach #

There are 3 problems to solve in this problem: how to find the next permutation; how to generate the smallest permutation when the next permutation does not exist; and how to modify in place. First solve the first problem: how to find the next permutation. The next permutation is to find a lexicographical order greater than the current arrangement, with the smallest possible increase. Therefore, only one in-place swap between a smaller number and a larger number can be made. In addition, the index of the smaller number should be as far to the right as possible, and the larger number should also be as small as possible. After the in-place swap, the numbers to the right of the larger number also need to be rearranged in ascending order. Only after such a swap can the next permutation be generated. Take the permutation [8,9,6,10,7,2] as an example: the pair of “smaller number” and “larger number” that meets the conditions is 6 and 7, satisfying that the “smaller number” is as far to the right as possible and the “larger number” is as small as possible. After the swap, the permutation becomes [8,9,7,10,6,2]. At this point, we can rearrange the sequence to the right of the “smaller number”, and the sequence becomes [8,9,7,2,6,10].
Step 1: find i in nums[i] such that nums[i] < nums[i+1]. At this point, the smaller number is nums[i], and [i+1, n) must be a descending interval. Step 2: if such an i is found, then in the descending interval [i+1, n), search from back to front for the first j such that nums[i] < nums[j]. At this point, the larger number is nums[j]. Step 3: swap nums[i] and nums[j]. At this point, the interval [i+1, n) must be in descending order. Finally, swap the elements in the interval [i+1, n) in place to make it ascending; there is no need to sort this interval.
If no valid index i can be found in the first step, it means the current sequence is already the largest permutation. Then the third step should be executed directly to generate the smallest permutation.

Code #

package leetcode

// Solution 1
func nextPermutation(nums []int) {
	i, j := 0, 0
	for i = len(nums) - 2; i >= 0; i-- {
		if nums[i] < nums[i+1] {
			break
		}
	}
	if i >= 0 {
		for j = len(nums) - 1; j > i; j-- {
			if nums[j] > nums[i] {
				break
			}
		}
		swap(&nums, i, j)
	}
	reverse(&nums, i+1, len(nums)-1)
}

func reverse(nums *[]int, i, j int) {
	for i < j {
		swap(nums, i, j)
		i++
		j--
	}
}

func swap(nums *[]int, i, j int) {
	(*nums)[i], (*nums)[j] = (*nums)[j], (*nums)[i]
}

// Solution 2
// [2,(3),6,5,4,1] -> 2,(4),6,5,(3),1 -> 2,4, 1,3,5,6
func nextPermutation1(nums []int) {
	var n = len(nums)
	var pIdx = checkPermutationPossibility(nums)
	if pIdx == -1 {
		reverse(&nums, 0, n-1)
		return
	}

	var rp = len(nums) - 1
	// start from right most to leftward,find the first number which is larger than PIVOT
	for rp > 0 {
		if nums[rp] > nums[pIdx] {
			swap(&nums, pIdx, rp)
			break
		} else {
			rp--
		}
	}
	// Finally, Reverse all elements which are right from pivot
	reverse(&nums, pIdx+1, n-1)
}

// checkPermutationPossibility returns 1st occurrence Index where
// value is in decreasing order(from right to left)
// returns -1 if not found(it's already in its last permutation)
func checkPermutationPossibility(nums []int) (idx int) {
	// search right to left for 1st number(from right) that is not in increasing order
	var rp = len(nums) - 1
	for rp > 0 {
		if nums[rp-1] < nums[rp] {
			idx = rp - 1
			return idx
		}
		rp--
	}
	return -1
}