powerset.go

package main

import (
	"bytes"
	"fmt"
	"strconv"
)

type elem interface {
	Eq(elem) bool
	fmt.Stringer
}

type Int int

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

type set []elem

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

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
}

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

func (s set) powerSet() set {
	r := set{set{}}
	for _, es := range s {
		var u set
		for _, er := range r {
			er := er.(set)
			u = append(u, append(er[:len(er):len(er)], es))
		}
		r = append(r, u...)
	}
	return r
}

func main() {
	var s set
	for _, i := range []Int{1, 2, 3} {
		s.add(i)
	}
	ps := s.powerSet()
	fmt.Println(ps)
}