-
Notifications
You must be signed in to change notification settings - Fork 0
/
permutations.go
65 lines (52 loc) · 1.65 KB
/
permutations.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
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
package projecteuler
// Permutations calculates and returns permutations of limit elements, or until f returns true
func Permutations(limit byte, f func(...interface{}) bool, args ...interface{}) (permutations [][]byte) {
starting := make([]byte, 0, limit)
changing := make([]byte, 0, limit)
for i := byte(0); i < limit; i++ {
changing = append(changing, i)
}
permutations, _ = doPerms(starting, changing, permutations, f, args...)
return
}
func doPerms(starting, changing []byte, perms [][]byte, f func(...interface{}) bool, args ...interface{}) (
[][]byte, bool) {
var halt bool
if len(changing) == 1 {
currPerm := make([]byte, cap(starting))
copy(currPerm, starting)
currPerm[cap(starting)-1] = changing[0]
return processPerm(currPerm, perms, f, args...)
}
for i := 0; i < len(changing); i++ {
starting = append(starting, changing[i])
newChanging := cutOutIndex(changing, i)
perms, halt = doPerms(starting, newChanging, perms, f, args...)
if halt {
return perms, true
}
starting = starting[:len(starting)-1]
}
return perms, false
}
func processPerm(currPerm []byte, perms [][]byte, f func(...interface{}) bool, args ...interface{}) (
resPerms [][]byte, retValue bool) {
resPerms = append(perms, currPerm)
if f != nil {
args = append(args, currPerm)
if f(args...) {
retValue = true
}
args = args[:len(args)-1]
}
return
}
func cutOutIndex(changing []byte, index int) (newChanging []byte) {
start := make([]byte, index)
copy(start, changing[:index])
end := make([]byte, len(changing)-index-1)
copy(end, changing[index+1:])
newChanging = append(newChanging, start...)
newChanging = append(newChanging, end...)
return
}