-
-
Notifications
You must be signed in to change notification settings - Fork 2.6k
/
next_permutation.go
39 lines (34 loc) · 1.15 KB
/
next_permutation.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// A practice to find lexicographically next greater permutation of the given array of integers.
// If there does not exist any greater permutation, then print the lexicographically smallest permutation of the given array.
// The implementation below, finds the next permutation in linear time and constant memory and returns in place
// time complexity: O(n)
// space complexity: O(1)
// Useful reference: https://www.geeksforgeeks.org/next-permutation/
package permutation
func NextPermutation(nums []int) {
pivot := 0
for pivot = len(nums) - 2; pivot >= 0; pivot-- {
if nums[pivot] < nums[pivot+1] {
break
}
}
if pivot < 0 {
// current permutation is the last and must be reversed totally
for l, r := 0, len(nums)-1; l < r; l, r = l+1, r-1 {
nums[l], nums[r] = nums[r], nums[l]
}
} else {
succ := 0
for succ = len(nums) - 1; succ > pivot; succ = succ - 1 {
if nums[succ] > nums[pivot] {
break
}
}
// Swap the pivot and successor
nums[pivot], nums[succ] = nums[succ], nums[pivot]
// Reverse the suffix part to minimize it
for l, r := pivot+1, len(nums)-1; l < r; l, r = l+1, r-1 {
nums[l], nums[r] = nums[r], nums[l]
}
}
}