Power set: Difference between revisions
→{{header|Go}}: language change required rewrite
m (TYPO) |
(→{{header|Go}}: language change required rewrite) |
||
Line 640:
=={{header|Go}}==
No native set type in Go.
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
"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.
// 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 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
if e.eq(ex) {
}
}
*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 {
if se.eq(te) {
}
return false
}
}
return true
}
// method to satify element interface
func (s set) String() string {
r := "{"
for _, e := range s {
if len(r) > 1 {
r += " "
Line 658 ⟶ 729:
}
// method required for task
▲func p(s set) set {
func
for _,
for _,
▲ ue[sr] = true
▲ }
▲ u[ue] = true
▲ }
▲ for su := range u {
▲ r[su] = true
}
r = append(r, u...)
}
return r
Line 677 ⟶ 743:
func main() {
var s set
for _, i := range []int{1, 2, 2, 3, 4, 4, 4} {
s.add(intEle(i))
}
fmt.Println(s)
fmt.Println(
ps := s.powerSet()
fmt.Println(ps)
fmt.Println("length =", len(ps))
}</lang>
Output:
<pre>
{
length = 4
{{
length = 16
</pre>
| |||