leetcode-go/medium/31.go

package main

import (
	"fmt"
)

// “字典序”
func nextPermutation(nums []int) {
	if len(nums) < 2 {
		return
	}
	// rfind first num descended 'ni'
	// 346987521 -> 34 '6' 987521
	i := len(nums) - 2
	for ; i >= 0 && nums[i] >= nums[i+1]; i-- {
	}
	if i != -1 {
		// find the last num 'nj' which is larger than 'ni'
		// swap 'nj', 'ni'
		// 34 '6' 987521 -> 34 '6' 98 '7' 521 -> 34 '7' 98 '6' 521
		j := i + 1
		for ; j+1 < len(nums) && nums[j+1] > nums[i]; j++ {
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	// reverse the sequence after pos 'i'
	// 34 '7' '986521' -> 34 '7' '125689'
	for l, r := i+1, len(nums)-1; l < r; l, r = l+1, r-1 {
		nums[l], nums[r] = nums[r], nums[l]
	}
}

func main() {
	a1 := []int{1, 2, 3}
	a2 := []int{3, 2, 1}
	a3 := []int{2, 3, 1}
	a4 := []int{1, 2, 2, 1}
	nextPermutation(a1)
	nextPermutation(a2)
	nextPermutation(a3)
	nextPermutation(a4)
	fmt.Println(a1)
	fmt.Println(a2)
	fmt.Println(a3)
	fmt.Println(a4)
}