I've been implementing some Python code in Go to learn the language. In
Python this will generate a Set Partition. The Go equivalent follows.
The Go runs fine for list element sizes 2 and 3 (which means the recursion
is running properly). Also 4 but at 5 and above it generates the intial
sets and then just stops. So on my machine I get 25 partitions for 5
elements and it should continue to 52. Similar results for larger number,
with 9 generating 213 sets against Python's 21147. So, I got over the lack
of lists by using slices, I got used to the global nature of variables. I
love the language but this has me confused. Any thoughts please?
---
def get_partitions(ss, out = []):
if len(ss) <= 1:
return [ss]
for i in range(2**len(ss)//2):
parts = [[], []]
for item in ss:
parts[i&1].append(item)
i >>= 1
for b in get_partitions(parts[1], []):
if b and not isinstance(b[0], list):
b = [b]
out.append([parts[0]]+ b)
return out
sp = get_partitions(["1", "2", "3", "4", "5"])
---
package main
import (
"fmt"
)
func get_partitions(set []string, out [][][]string) [][][]string {
out = out[:1]
out[0] = out[0][:1]
out[0][0] = out[0][0][:1]
if len(set) <= 1 {
out[0][0] = set
return out
}
for j := 0; j < len(set)*len(set)/2; j++ {
i := j
parts := make([][]string, 2)
for _, item := range set {
parts[i&1] = append(parts[i&1], item)
i >>= 1
}
pts := get_partitions(parts[1], out)
for _, pt := range pts {
i3 := len(out) - 1
if len(out[i3][len(out[i3])-1]) == 0 {
out[i3][len(out[i3])-1] = parts[0]
} else {
out = append(out, [][]string{})
i3 += 1
out[i3] = append(out[i3], parts[0])
}
if len(pt[0]) > 0 {
for ptidx, _ := range pt {
out[i3] = append(out[i3], pt[ptidx])
}
}
}
}
return out
}
func main() {
set := []string{"1", "2", "3", "4", "5"}
var out [][][]string
out = make([][][]string, 1) // create & initialize 3D slice
out[0] = make([][]string, 1)
out[0][0] = make([]string, 1)
t0 := time.Now()
ppp := get_partitions(set, out)
fmt.Println(len(ppp))
}
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
