-
Notifications
You must be signed in to change notification settings - Fork 2
/
permutation.go2
81 lines (69 loc) · 1.67 KB
/
permutation.go2
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package main
// vim:set ft=go:
// snip ------------------------------------------------------------------------
// Modify the slice to the next pattern of its permutations in lexicographic order.
// It returns true if it has next permutation.
// Otherwise, the slice is the last pattern of permutations, it returns false.
//
// Example:
//
// sort.Ints(a)
// for ok := true; ok ; ok = NextPermutation(a) {
// fmt.Println(a)
// }
//
func NextPermutation[T Ordered](a []T) bool {
return Permutation(a, Less[T])
}
// Modify the slice to the previous pattern of its permutations in lexicographic order.
func PrevPermutation[T Ordered](a []T) bool {
return Permutation(a, More[T])
}
// Narayana Pandita's algorithm whitch generates lexicographic permutations
func Permutation[T any](a []T, less func(x, y T) bool) bool {
i := len(a) - 2
// Find the right most incresing elements a[i] and a[i+1]
for 0 <= i && !less(a[i], a[i+1]) {
i--
}
if i == -1 {
return false
}
j := i + 1
// Find the smallest element that is greater than a[i] in a[i+1:]
for k := j + 1; k < len(a); k++ {
// a[i] < a[k] && a[k] <= a[j]
if less(a[i], a[k]) && !less(a[j], a[k]) {
j = k
}
}
a[i], a[j] = a[j], a[i]
Reverse(a[i+1:])
return true
}
// Heap's algorithm which generates non-lexicographic permutations.
// It less swaps elements than Narayana Pandita's algorithm.
func DoPermutationHeap(a []int, fn func([]int)) {
n := len(a)
c := make([]int, n)
i := 0
swap := func(i, j int) {
a[i], a[j] = a[j], a[i]
}
fn(a)
for i < n {
if c[i] < i {
if i%2 == 0 {
swap(0, i)
} else {
swap(c[i], i)
}
fn(a)
c[i]++
i = 0
} else {
c[i] = 0
i++
}
}
}