Newbie Implementation of Set Partitions Generator

[john lynch]

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))
}

[Ian Lance Taylor]

On Thu, Oct 12, 2017 at 11:57 PM, john lynch <mjohn...@gmail.com> wrote:
>
> 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?

I don't know what you are trying to do but if I were you I would look
closely at the way you are passing slices around. When you pass the
slice `out` in the recursive call, it will be modified by the function
you are calling. So you seem to be trying to build partitions in out
while also passing it down in a recursive call that clobbers some
elements.

Ian

[Michael Jones]

Generating set partitions is efficiently performed by [the second] Algorithm H in Knuth's Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1. It appears on page 416. 

Counting the number of set partitions means evaluating the Bell numbers, which is easily done by table summation.

Efficiently programming the generation of set partitions depends on what you need contextually, either all of the partitions at once as a list of solutions, or one at a time in the spirit of a solution generator.

In the second case, a generator for set partitions, it is possible to generate them in "shape order"; a 4-tuple broken into blocks of length 4, 3+1, 2+2, 2+1+1, 1+1+1+1. (The five "shapes" being the integer partition of the number 4). If you were to create slices of these cardinalities in Go and just fill in the values, then the generator would have a minimal allocation overhead, given that there may be many instances of some shapes. 

It is also possible to skip the generation of the physical subsets altogether, by generating the manifests for the various blocks. For example, dividing "ABCD" into AD+B+C can be represented by the value "1231" meaning that A and D are in group 1, B is in 2, and C is in group 3. I have done this scheme in a combination generator before in Go with respectable efficiency:

BenchmarkOrderedRate1-8      300000000          4.65 ns/op

BenchmarkOrderedRate2-8      100000000         10.5 ns/op

BenchmarkOrderedRate3-8      100000000         17.1 ns/op

BenchmarkOrderedRate4-8      100000000         24.1 ns/op

BenchmarkOrderedRate5-8      50000000         32.5 ns/op

BenchmarkOrderedRate6-8      50000000         39.5 ns/op

BenchmarkOrderedRate7-8      30000000         46.5 ns/op

BenchmarkOrderedRate8-8      30000000         53.0 ns/op

BenchmarkOrderedRate9-8      20000000         59.6 ns/op

BenchmarkOrderedRate10-8    20000000         66.9 ns/op

BenchmarkOrderedRate11-8    20000000         75.9 ns/op

BenchmarkOrderedRate12-8    20000000         82.6 ns/op

BenchmarkOrderedRate13-8    20000000         88.9 ns/op

BenchmarkOrderedRate14-8    20000000         95.6 ns/op

BenchmarkOrderedRate15-8    20000000        102 ns/op

...and because i was able to use the "manifest" representation in my code, there is no allocation in the loops and even 15-element generation proceeds at 10 million iterations per second. I did not need a set partition generator, so I don't have code to offer, but the work is similar and the speeds should not be too different, at least for the manifest (aka "index") representation.

--
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+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Michael T. Jones
michae...@gmail.com

[john lynch]

Thanks Ian,

You are correct (although the post I submitted yesterday had the clobbering lines incorrect - that was one of my experiments to see if rebuilding the 3D slice differently would overcome the problem).   The code below is my original.

Yes, the function works by building fresh versions of out at each later and then reconstructing each set from the returned outs.

I am currently assuming that because it works for 2, 3, and 4 then somehow I'm doing something that causes my Go runtime (latest version running on Linux Mint 18 on an Intel i5) to return an answer before it has finished producing sets.

My next experiments will be to try to use the Gogland debug to establish why it stops.

package main

import (
    "fmt"

    "time"

)

func get_partitions(set []string, out [][][]string) [][][]string {

    out = make([][][]string, 1)

    out[0] = make([][]string, 1)

    out[0][0] = make([]string, 0)

    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, ppp [][][]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)

    elapsed := time.Since(t0)
    fmt.Printf("Took %s\n", elapsed)
    fmt.Printf("\nGot the partition: %v\n", ppp)
    fmt.Println(len(ppp))
}

[john lynch]

Thanks Michael,

I appreciate the information.   Because I'm trying to learn Go, I'm more interested in what should cause it to stop running part way through the process without generating an error.   It just seems bizarre to me but I'm sure it'll reveal an error in my thinking.

[john lynch]

"I'm sure it'll reveal an error in my thinking"

To avoid importing math I had changed my upper limit early on but I 'd misread it.

The critical line in error should be changed to:

for j := 0; j < int(math.Pow(2.0, float64(len(set)))/2.0); j++ {