README
¶
Go Set Implementation
What this project does
This package provides a generic interface and an in-memory implementation of finite sets in Go. It serves both as a practical utility and as a teaching tool for understanding set theory concepts through code.
Key features:
- Generic implementation supporting any comparable type.
- O(1) operations using hash-based storage.
- Complete set theory operations. (union, intersection, difference, etc.)
- Advanced operations like Cartesian product and power set.
- Comprehensive test coverage with examples from set theory.
- Clear documentation connecting mathematical concepts to implementation.
Why it's useful
Our set implementation helps you:
- Manage collections of unique elements efficiently
- Perform set operations with guaranteed performance characteristics
- Learn set theory through practical code examples
- See how mathematical concepts translate to Go code
Getting started
Installation
go get -u coderscompass.org/set
Basic Usage
package main
import (
"fmt"
"coderscompass.org/set"
)
func main() {
// Create sets
hobbits := set.NewHashSet[string]()
fellowship := set.NewHashSet[string]()
// Add elements
hobbits.Insert("Frodo")
hobbits.Insert("Sam")
fellowship.Insert("Frodo")
fellowship.Insert("Gandalf")
// Find intersection
hobbitFellows := hobbits.Intersection(fellowship)
// Result contains {"Frodo"}
expected := set.NewHashSet[string]()
expected.Insert("Frodo")
if !hobbitFellows.Equals(expected) {
fmt.Println("Expected hobbitFellows to be equal to expected")
} else {
fmt.Println("hobbitFellows is equal to expected")
}
// Advanced operations
product := set.CartesianProduct(hobbits, fellowship)
powerSet := set.PowerSet(hobbits)
// Print results using implicit string conversion
fmt.Println(product)
fmt.Println(powerSet)
}
Performance Guarantees
| Operation | Time Complexity |
|---|---|
| Insert/Remove | O(1) |
| Contains | O(1) |
| Intersection | O(min(n, m)) |
| Union | O(n + m) |
| Difference | O(m) |
| Cartesian Product | O(n × m) |
| Power Set | O(2^n) |
Here n and m are the sizes of the two sets involved in the operations.
Getting help
Project maintenance
Current Status
- Version:
- Go Version: >= 1.23
- Maintenance: Active
Contributing
We welcome contributions! See our Contributing Guide for details on:
- Code style and standards
- Development setup
- Test requirements
- Pull request process
Security
For security concerns, please review our Security Policy.
Learning Resources
- Set Theory Book: Comprehensive guide to set theory concepts
- pkgo.dev Documentation: API reference
License
This project is licensed under the MIT License - see the LICENSE file for details.
Contact
For questions or support, please contact us.
Documentation
¶
Overview ¶
Package set provides a generic set data interface and implementations of this interface.
The interface is based on the mathematical definition of a set and provides operations like union, intersection, difference, and subset relationships. The package also provides a map-based in-memory implementation of the Set interface called hashSet.
The CartesianProduct and PowerSet functions are also provided separately to avoid type dependency cycles while still maintaining the complete set of operations from set theory.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Pair ¶ added in v0.2.0
type Pair[T comparable] struct { First T Second T }
Pair represents an ordered pair of elements for use in Cartesian products.
type Set ¶
type Set[T comparable] interface { // Insert adds the element to the set. // If the element already exists, the set remains unchanged. Insert(elem T) // Remove deletes the element from the set. // If the element does not exist, the set remains unchanged. Remove(elem T) // Contains reports whether the element exists in the set. Contains(elem T) bool // Cardinality returns the number of elements (a natural, counting number) in this finite set. Cardinality() int // IsEmpty reports whether the set has no elements. IsEmpty() bool // Equals reports whether this set contains exactly the same elements as the other set. Equals(other Set[T]) bool // IsSubsetOf reports whether this set is a subset of the other set. // A set **X** is a subset of set **Y** if every element of **X** is also an element of **Y**. IsSubsetOf(other Set[T]) bool // IsSupersetOf reports whether this set is a superset of the other set. // A set **X** is a superset of set **Y** if every element of **Y** is also an element of **X**. IsSupersetOf(other Set[T]) bool // IsProperSubsetOf reports whether this set is a proper subset of the other set. // A set **X** is a proper subset of set **Y** if **X** is subset of **Y** and **X** ≠ **Y**. IsProperSubsetOf(other Set[T]) bool // IsProperSupersetOf reports whether this set is a proper superset of the other set. // A set **X** is a proper superset of set **Y** if **X** is superset of **Y** and **X** ≠ **Y**. IsProperSupersetOf(other Set[T]) bool // Union returns a new set containing all elements that are in either this set // or the other set (**X** ∪ **Y**). Union(other Set[T]) Set[T] // Intersection returns a new set containing all elements that are in both this set // and the other set (**X** ∩ **Y**). Intersection(other Set[T]) Set[T] // Difference returns a new set containing all elements that are in this set // but not in the other set (**X** \ **Y**). Difference(other Set[T]) Set[T] // SymmetricDifference returns a new set containing all elements that are in either this set // or the other set, but not in both (**X** Δ **Y**). SymmetricDifference(other Set[T]) Set[T] // ToSlice returns a slice containing all elements in the set. // **Note**: The order of elements is not guaranteed to be stable between calls. ToSlice() []T // String returns a string representation of the set. // For sets of strings, the elements are sorted lexicographically. String() string }
Set is a generic interface that defines the operations that can be performed on a set. A set is defined as an unordered collection of unique, arbitrary elements. The zero value of a set is an empty set.
func CartesianProduct ¶ added in v0.2.0
func CartesianProduct[T comparable](s1, s2 Set[T]) Set[Pair[T]]
CartesianProduct returns a new set containing all possible ordered pairs (x, y) where x is from the first set and y is from the second set. For sets A and B, it returns A × B = {(x, y) | x ∈ A, y ∈ B}.
For example, if A = {1, 2} and B = {3, 4}, then CartesianProduct(A, B) = {(1, 3), (1, 4), (2, 3), (2, 4)}.
func NewHashSet ¶
func NewHashSet[T comparable]() Set[T]
NewHashSet creates and returns a new empty set.
func PowerSet ¶ added in v0.2.0
func PowerSet[T comparable](s Set[T]) Set[Set[T]]
PowerSet returns a slice containing all possible subsets of the input set. For a set S, it returns P(S) = {T | T ⊆ S}.
For a set with n elements, the power set contains 2^n elements. For example, if S = {1, 2}, then PowerSet(S) = {{}, {1}, {2}, {1, 2}}.
Source Files