Power set: Difference between revisions

Content added Content deleted

Inline

@@ Line 640: / Line 640: @@
 =={{header|Go}}==
-No native set type in Go.  Instead the associative array trick mentioned in the task description works well in Go.  Also this is a good application of the empty interface type, interface{}, to allow different types of objects to be stored in a set.
+No native set type in Go.  While the associative array trick mentioned in the task description works well in Go in most situations, it does not work here because we need sets of sets, and converting a general set to a hashable value for a map key is non-trivial.
+Instead, this solution uses a simple (non-associative) slice as a set representation.  To ensure uniqueness, the element interface requires an equality method, which is used by the
+set add method.  Adding elements with the add method ensures the uniqueness property.
+The power set method implemented here does not need the add method though.  The algorithm
+ensures that the result will be a valid set as long as the input is a valid set.  This allows the more efficient append function to be used.
 <lang go>package main
-import "fmt"
+import (
+    "fmt"
+    "strconv"
+)
+// types needed to implement general purpose sets are element and set
-type set map[interface{}]bool
+// element is an interface, allowing different kinds of elements to be
+// implemented and stored in sets.
+type element interface {
+    // an element must be disinguishable from other elements to satisfy
+    // the mathematical definition of a set.  a.eq(b) must give the same
+    // result as b.eq(a).
+    eq(element) bool
+    // String result is used only for printable output.  Given a, b where
+    // a.eq(b), it is not required that a.String() == b.String().
+    String() string
+}
+// integer type satisfying element interface
+type intEle int
+func (i intEle) eq(e element) bool {
+    if j, ok := e.(intEle); ok {
+        return i == j
+    }
+    return false
+}
+func (i intEle) String() string {
+    return strconv.Itoa(int(i))
+}
+// set type implemented as a simple list.  methods will be added to
+// make it satisfy the element interface, allowing sets of sets.
+type set []element
+// uniqueness of elements can be ensured by using add method
+func (s *set) add(e element) {
+    for _, ex := range *s {
+        if e.eq(ex) {
+            return
+        }
+    }
+    *s = append(*s, e)
+}
+// method to satify element interface
+func (s set) eq(e element) bool {
+    t, ok := e.(set)
+    if !ok {
+        return false
+    }
+    if len(s) != len(t) {
+        return false
+    }
+sLoop:
+    for _, se := range s {
+        for _, te := range t {
+            if se.eq(te) {
+                continue sLoop
+            }
+            return false
+        }
+    }
+    return true
+}
+// method to satify element interface
 func (s set) String() string {
     r := "{"
-    for e := range s {
+    for _, e := range s {
         if len(r) > 1 {
             r += " "
@@ Line 658: / Line 729: @@
 }
+// method required for task
-func p(s set) set {
-    r := set{make(set): true}
+func (s set) powerSet() set {
-    for es := range s {
+    r := set{set{}}
-        u := make(set)
+    for _, es := range s {
-        for er := range r {
+        var u set
-            ue := set{es: true}
+        for _, er := range r {
-            for sr := range er.(set) {
+            u = append(u, append(er.(set), es))
-                ue[sr] = true
-            }
-            u[ue] = true
-        }
-        for su := range u {
-            r[su] = true
         }
+        r = append(r, u...)
     }
     return r
@@ Line 677: / Line 743: @@
 func main() {
+    var s set
-    s := set{1: true, 2: true, 3: true, 4: true}
+    for _, i := range []int{1, 2, 2, 3, 4, 4, 4} {
+        s.add(intEle(i))
+    }
     fmt.Println(s)
-    fmt.Println(p(s))
+    fmt.Println("length =", len(s))
+    ps := s.powerSet()
+    fmt.Println(ps)
+    fmt.Println("length =", len(ps))
 }</lang>
+Output:
-Output:  Like mathematical sets, Go maps are not ordered!  Iteration returns members in no particular order.
 <pre>
-{4 1 2 3}
+{1 2 3 4}
+length = 4
-{{4 3} {1 2 3} {4 2 3} {3} {1 3} {4 1 2 3} {4 1 3} {2 3} {1} {4 1} {} {4} {2} {2 1} {4 2} {4 1 2}}
+{{} {1} {2} {1 2} {3} {1 3} {2 3} {1 2 3} {4} {1 4} {2 4} {1 2 4} {3 4} {1 3 4} {2 3 4} {1 2 3 4}}
+length = 16
 </pre>