Rosetta Code

Power set: Difference between revisions

Page Discussion

Power set (view source)

Revision as of 04:33, 19 June 2016

910 bytes added ,  8 years ago
→‎{{header|Go}}: Bug fix. Oschmid identified the bug, but the fix had problems. Here's a better fix.
m (added whitespace around a link.)
(→‎{{header|Go}}: Bug fix. Oschmid identified the bug, but the fix had problems. Here's a better fix.)
Line 1,028:
set add method. Adding elements with the add method ensures the uniqueness property.
 
TheWhile the "add" and "has" methods make a usable set type, the power set method implemented here doescomputes nota needresult directly without using 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.
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 (
"bytes"
"fmt"
"strconv"
)
 
Line 1,043 ⟶ 1,042:
// implemented and stored in sets.
type elem interface {
// an element must be distinguishable from other elements to satisfy
// the mathematical definition of a set. a.eq(b) must give the same
// result as b.eq(a).
Eq(elem) 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().
fmt.Stringer
}
 
Line 1,056 ⟶ 1,055:
 
func (i Int) Eq(e elem) bool {
j, ok := e.(Int)
return ok && i == j
}
 
func (i Int) String() string {
return strconv.Itoa(int(i))
}
 
Line 1,070 ⟶ 1,069:
// uniqueness of elements can be ensured by using add method
func (s *set) add(e elem) {
if !s.has(e) {
*s = append(*s, e)
}
}▼
}
 
func (s *set) has(e elem) bool {
for _, ex := range *s {
if e.Eq(ex) {
return true
}
}
}
}
return false
▲ }
 
func (s set) ok() bool {
for i, e0 := range s {
for _, e1 := range s[i+1:] {
if e0.Eq(e1) {
return false
}
}
}
return rtrue▼
}
 
// elem.Eq
func (s set) Eq(e elem) bool {
t, ok := e.(set)
if !ok {
return false
}
}
if len(s) != len(t) {
return false
}
}
for _, se := range s {
if !t.has(se) {
return false
}
}
}
}
return true
}
 
// elem.String
func (s set) String() string {
if len(s) == 0 {
return "∅"
}
}
var buf bytes.Buffer
buf.WriteRune('{')
for i, e := range s {
if i > 0 {
buf.WriteRune(',')
}
}
buf.WriteString(e.String())
}
}
buf.WriteRune('}')
return buf.String()
}
 
// method required for task
func (s set) powerSet() set {
r := set{set{}}
for _, es := range s {
var u set
for _, er := range r {
u = append(u, copyAndAppend( er := er.(set), es))
u = append(u, append(er[:len(er):len(er)], es))
}
}
r = append(r, u...)
}
}
▲ return r
return r
}
 
// regular append() will edit in place, creating duplicate subsets for larger set inputs
func copyAndAppend(slice []string, elem string) []string {
return append(append([]string(nil), slice...), elem)
}
 
func main() {
var s set
for _, i := range []Int{1, 2, 2, 3, 4, 4, 4} {
s.add(i)
}
}
fmt.Println(" s:", s, "length:", len(s))
ps := s.powerSet()
fmt.Println(" 𝑷(s):", ps, "length:", len(ps))
 
fmt.Println("\n(extra credit)")
var empty set
fmt.Println(" empty:", empty, "len:", len(empty))
ps = empty.powerSet()
fmt.Println(" 𝑷(∅):", ps, "len:", len(ps))
ps = ps.powerSet()
fmt.Println("𝑷(𝑷(∅)):", ps, "len:", len(ps))
 
fmt.Println("\n(regression test for earlier bug)")
s = set{Int(1), Int(2), Int(3), Int(4), Int(5)}
fmt.Println(" s:", s, "length:", len(s), "ok:", s.ok())
ps = s.powerSet()
fmt.Println(" 𝑷(s):", "length:", len(ps), "ok:", ps.ok())
for _, e := range ps {
if !e.(set).ok() {
panic("invalid set in ps")
}
}
}</lang>
{{out}}
Line 1,156 ⟶ 1,174:
s: {1,2,3,4} length: 4
𝑷(s): {∅,{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
 
(extra credit)
empty: ∅ len: 0
𝑷(∅): {∅} len: 1
𝑷(𝑷(∅)): {∅,{∅}} len: 2
 
(regression test for earlier bug)
s: {1,2,3,4,5} length: 5 ok: true
𝑷(s): length: 32 ok: true
</pre>
 
Sonia
1,707

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/74424"