-
Notifications
You must be signed in to change notification settings - Fork 2
/
factorial_number_system.go
53 lines (40 loc) · 1.11 KB
/
factorial_number_system.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
package main
import "fmt"
func main() {
elements := generateInput()
perms := permutations(elements)
for _, perm := range perms {
fmt.Println(perm)
}
}
// Using the Factorial Number System
// See also: https://en.wikipedia.org/wiki/Factorial_number_system
func permutations(input []string) [][]string {
var result [][]string
factorials := generateFactorials(len(input))
for i := 0; i < factorials[len(input)]; i++ {
var permutation []string
tmp := make([]string, len(input))
copy(tmp, input)
positionCode := i
for position := len(input); position > 0; position-- {
selected := positionCode / factorials[position-1]
permutation = append(permutation, tmp[selected])
positionCode = positionCode % factorials[position-1]
tmp = append(tmp[:selected], tmp[selected+1:]...)
}
result = append(result, permutation)
}
return result
}
func generateFactorials(size int) []int {
result := []int{1}
for i := 1; i <= size; i++ {
result = append(result, result[i-1]*i)
}
return result
}
func generateInput() []string {
return []string{"A", "B", "C", "D"}
// return []string{"1", "2", "3"}
}