Next Permutation

1. Problem Description

Implement a function that obtains the next permutation. The algorithm must rearrange the given sequence of numbers into the next lexicographically greater permutation.

If no next greater permutation exists, rearrange the numbers into the smallest possible permutation (that is, ascending order).

The modification must be performed in place using only constant extra space.

2. Approach

1. Approach 1
   • Brute force
   • Enumerate all permutations first
   • Deduplicate and sort them
   • Find the next permutation
2. Approach 2
   • Swap a larger number on the right with a smaller number on the left

3. Implementation

3.1. Brute Force

package main

import (
	"reflect"
	"sort"
)

func nextPermutation(nums []int)  {
	visited := make(map[int]bool, 0)
	path := make([]int, 0)
	allPaths := make([][]int, 0)
	permuteDFS(nums, 0, &allPaths, &path, visited)

	sort.Slice(allPaths, func(i,j int) bool {
		a := allPaths[i]
		b := allPaths[j]
		for i := 0; i < len(a); i++ {
			if a[i] < b[i] {
				return true
			}else if a[i] == b[i] {
				continue
			}else {
				return false
			}
		}

		return false
	})

	for i, v := range allPaths {
		if reflect.DeepEqual(v, nums) {
			res := allPaths[(i+1) % len(allPaths)]
			for i := 0; i < len(nums); i++ {
				nums[i] = res[i]
			}
			return
		}
	}

	return
}

func exists(path *[]int, allPaths *[][]int) bool {
	for i := 0; i < len(*allPaths); i++ {
		if reflect.DeepEqual((*allPaths)[i], *path) {
			return true
		}
	}

	return false
}


func permuteDFS(nums []int, index int, allPaths *[][]int, path *[]int, visited map[int]bool) {
	if index == len(nums) {
		if exists(path, allPaths) {
			return
		}
		dst := make([]int, len(nums))
		copy(dst, *path)
		*allPaths = append(*allPaths, dst)
		return
	}

	for i := 0; i < len(nums); i++ {
		if visited[i] {
			continue
		}

		visited[i] = true
		*path = append(*path, nums[i])

		permuteDFS(nums, index+1, allPaths, path, visited)

		visited[i] = false
		*path = (*path)[:len(*path)-1]
	}
}

3.2. Swap

func nextPermutation2(nums []int) {
	if len(nums) <= 1 {
		return
	}

	// Find the first ascending pair [i,j] from right to left
	i, j := len(nums)-2, len(nums)-1
	for i >= 0 && nums[i] >= nums[j] {
		i--
		j--
	}

	if i >= 0 {
		// Find the first number [k] greater than [i] from right to left
		k := len(nums) - 1
		for nums[i] >= nums[k] {
			k--
		}
		// Swap [i] and [k]
		nums[i], nums[k] = nums[k], nums[i]
	}

	// The remaining [j,end] range is descending; reverse it
	reverse(nums, j, len(nums)-1)
}

func reverse(nums []int, left int, right int) {
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

4. References

• Detailed Next Permutation Algorithm: Idea + Derivation + Steps; If You Still Don’t Get It, I Lose! - Next Permutation - LeetCode