Next lexicographic permutation (iterative)

next_permutation.go

func nextPermutation(a []int) {
	// Find the greatest index i such that a[i] < a[i + 1]
	i := len(a) - 2
	for i >= 0 && a[i] >= a[i+1] {
		i--
	}
	if i >= 0 {
		// Find the greatest index j > i such that a[i] < a[j]; such an index
		// exists because a[i] < a[i + 1]
		j := len(a) - 1
		for a[i] >= a[j] {
			j--
		}
		a[i], a[j] = a[j], a[i]
	}
	reverse(a[i+1:])
}

func reverse(a []int) {
	for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
		a[i], a[j] = a[j], a[i]
	}
}