CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Sets

1. Starter Code
2. Creating Sets
3. Looping over Sets
4. Set Utilities
5. Properties of Sets
   1. Sets are Unordered
   2. Elements are Unique
   3. Sets are Very Efficient
6. The Speed of Sets
7. Some Worked Examples Using Sets

1. Starter Code
   Sets are not a data type native to Go, so we provide you with an implementation of sets accessible via the cs112 library. For a day, we used the implementation of sets here. We'll leave the link up in case you want to access the old implementation.


2. Creating Sets
   • Create an empty set
     package main import ( "fmt" "github.com/CMU15-112/golang" ) func main() { s := make(cs112.IntSet) fmt.Println(s) }
   
   
   • Adding elements to a set
     package main import ( "fmt" "github.com/CMU15-112/golang" ) func main() { s := make(cs112.IntSet) s.LoadSlice([]int{1,2,3,4,5,6}) fmt.Println(s) }


3. Using Sets
   • Basics
     
     package main import ( "fmt" "github.com/CMU15-112/golang" ) func main() { // Sets can do many of the same things as lists and tuples... s := make(cs112.IntSet) s.LoadSlice([]int{2, 3, 5}) fmt.Println(len(s)) // prints 3 fmt.Println(s.Has(2)) // prints true fmt.Println(s.Has(4)) // prints false s.Remove(3) // removes 3 from the set fmt.Println(s) }
     
     
   • Looping Over Sets
     
     package main import ( "fmt" "github.com/CMU15-112/golang" ) func main() { /* You can loop over a set by converting it to a slice and then looping over that slice */ s := make(cs112.IntSet) s.LoadSlice([]int{2, 3, 5}) for _, elem := range s.ToSlice() { fmt.Println(elem) } }


4. Set Utilities
   package main import ( "fmt" "github.com/CMU15-112/golang" ) func main() { // The cs112 library exposes all of the following functionality // Making sets s1 := make(cs112.IntSet) s2 := make(cs112.StringSet) // Loading sets from slices s1.LoadSlice([]int{1,2,3,4}) s2.LoadSlice([]string{"a", "b", "c"}) // Converting sets into slices fmt.Println(s1.ToSlice()) fmt.Println(s2.ToSlice()) // Taking the union of two sets s3 := make(cs112.IntSet) s3.LoadSlice([]int{4,5}) fmt.Println(s1.Union(s3)) }


5. Properties of Sets
   Though sets are very similar to lists and tuples, they have a few important differences...
   
   
   1. Sets are Unordered
      
      /* Elements may be arranged in a different order than they are provided and we cannot index into the set */ package main import ( "fmt" "github.com/CMU15-112/golang" ) func main() { a := []int{1,2,3,4,5,6} s := make(intSet) for _, elem := range a { s.Add(elem) } fmt.Println(s) // Prints differently every time we run }
   
   
   2. Elements are Unique
      
      // Sets can also only hold one of each unique element. Duplicates are removed. package main import ( "fmt" "github.com/CMU15-112/golang" ) func main() { a := []int{2,2,2,2,2,2,2} s := make(intSet) for _, elem := range a { s.Add(elem) } fmt.Println(s) // Prints {2} fmt.Println(len(s)) // Prints 1 }
   
   
   3. Sets are Very Efficient
      The whole point of having sets is because they are very efficient, in fact O(1), for most common operations including adding elements, removing elements, and checking for membership.


6. The Speed of Sets
   A practical example of how sets are faster than lists is shown below:
   Note: Time is static in the Go Playground, so this example must be run on your computer. Don't forget to add our sets code!
   package main import ( "fmt" "time" "github.com/CMU15-112/golang" ) func main() { // 0. Set up a slice and set with n elements (0 to n) n := 100000 a := make([]int, 0) s := make(intSet) for i := 0; i < n; i += 1 { a = append(a, i) s.Add(i) } // 1. For each number 0 to n, check for slice membership and time it fmt.Println("Starting non-hashing search") start := time.Now() count := 0 for i := 0; i < n; i += 1 { if cs112.Contains(a, i) { count += 1 } } fmt.Println("Counted", n, "and took", time.Since(start)) // 2. Repeat for sets fmt.Println("Starting hashed search") start = time.Now() count = 0 for i := 0; i < n; i += 1 { if s.Has(i) { count += 1 } } fmt.Println("Counted", n, "and took", time.Since(start)) }


7. Some Worked Examples Using Sets
   
   • isPermutation(L)
     package main import ( "fmt" "github.com/CMU15-112/golang" ) func isPermutation(L []int) bool { /* return True if L is a permutation of [0,...,n-1] and False otherwise */ setL := make(cs112.IntSet) setL.LoadSlice(L) for i := 0; i < len(L); i += 1 { if !setL.Has(i) { return false } } return true } func testIsPermutation() { fmt.Print("Testing isPemutation...") cs112.assert(isPermutation([]int{0, 2, 1, 4, 3}) == true) cs112.assert(isPermutation([]int{0, 1, 3}) == false) fmt.Println("Passed!") } func main() { testIsPermutation() }
   
   
   • repeats(L)
     package main import ( "fmt" "github.com/CMU15-112/golang" ) func repeats(L []int) intSet { seen := make(intSet) seenAgain := make(intSet) for _, elem := range L { if seen.Has(elem) { seenAgain.Add(elem) } seen.Add(elem) } return seenAgain } func main() { fmt.Println(repeats([]int{1,2,3,2,1})) fmt.Println(repeats([]int{1,2,3,2,2,4})) fmt.Println(repeats([]int{1,2,3,4,5,6,7,8})) }