public
Created

Calculate Partition in Go

  • Download Gist
partition.go
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
package main
 
import "fmt"
import "sort"
 
type EMPTY struct {}
 
var PRESENT EMPTY = EMPTY{}
 
func partition(val int) []string {
set := make(map[string]EMPTY)
for i := 1; i<=val;i++ {
for _,result := range worker([]int{i},val-i) {
set[fmt.Sprintf("%v",result)]=PRESENT
}
}
out := make([]string,len(set))
pos :=0
for key := range set {
out[pos] = key
pos++
}
sort.Strings(out)
return out
}
 
func worker(already []int, val int) [][]int {
if val == 0 {
sort.Ints(already)
return [][]int{already}
}
out := [][]int {}
for i := 1;i<=val;i++ {
out = append(out,worker(append(already,i),val-i)...)
}
return out
}
 
func main() {
for i := 0;i<10;i++ {
result := partition(i)
fmt.Printf("%d (%d): %v\n",i,len(result),result)
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.