Computer Science 15-112, Spring 2012
Class Notes:  Sets

1. Required Reading
2. Quick Example
3. Properties of Sets
   1. Sets are Unordered
   2. Elements are Unique
   3. Elements May be of Mixed Types
   4. Elements Must Be Immutable
   5. Sets are Efficient
4. Create a Set
5. Set Operations
6. Example Using Sets

1. Required Reading
   1. The Python Tutorial, Ch 5.4 (Sets)
   2. The Python Standard Library, Ch 8.7 (Sets)
   3. The Python Standard Library, Ch 5.7 (Set Types)
       
2. Quick Example

   s = set([2,3,5,7,9])
   print (3 in s)          # prints True
   print (4 in s)          # prints False
   for x in xrange(10):
       if (x not in s):
           print x,        # prints 0 1 4 6 8

3. Properties of Sets
   1. Sets are Unordered

      s = set([2,4,8])
      print s            # prints set([8, 2, 4])
      for element in s:
          print element, # prints 8 2 4

   2. Elements are Unique

      s = set([2,2,2])
      print s            # prints set([2])
      print len(s)       # prints 1

   3. Elements May be of Mixed Types

      s = set([2,True,"yes"])
      print s            # prints set([True, 2, 'yes'])

   4. Elements Must Be Immutable

      a = ["lists", "are", "mutable"]
      s = set([a])       # TypeError: unhashable type: 'list'
      print s
      
      s1 = set(["sets", "are", "mutable", "too"])
      s2 = set([s1])     # TypeError: unhashable type: 'set'
      print s

   5. Sets are Efficient

      # 0. Preliminaries
      import time
      n = 20000
      
      # 1. Create a list [2,4,6,...,n] then check for membership
      # among [1,2,3,...,n] in that list.
      print "Using a list...",
      start = time.time()
      a = range(2,n+1,2)
      count = 0
      for x in xrange(n+1):
          if x in a:
              count += 1
      end = time.time()
      print "time = %0.4f seconds" % (end - start)
      
      # 2. Repeat, using a set
      print "Using a set...",
      start = time.time()
      a = range(2,n+1,2)
      s = set(a)
      count = 0
      for x in xrange(n+1):
          if x in s:
              count += 1
      end = time.time()
      print "time = %0.4f seconds" % (end - start)

4. Create a Set

   # Create an empty set
   s = set()
   print s     # prints set([])
   
   # Create a set from a list
   s = set(["cat", "cow", "dog"])
   print s     # prints set(['dog', 'cow', 'cat'])
   
   # Create a set from any iterable object
   s = set("wahoo")
   print s     # surprised?

5. Set Operations
   See tables here.
    
   1. Operations on a set
       

      Operation	Result
      len(s)	cardinality of set s
      s.copy()	new set with a shallow copy of s
      s.pop()	remove and return an arbitrary element from s; raises KeyError if empty
      s.clear()	remove all elements from set s

       

   2. Operations on a set and an element
       

      Operation	Result
      x in s	test x for membership in s
      x not in s	test x for non-membership in s
      s.add(x)	add element x to set s
      s.remove(x)	remove x from set s; raises KeyError if not present
      s.discard(x)	removes x from set s if present

       

   3. Operations on two sets (or a set and an iterable)
       

      Operation	Equivalent	Result
      s.issubset(t)	s <= t	test whether every element in s is in t
      s.issuperset(t)	s >= t	test whether every element in t is in s
      s.union(t)	s | t	new set with elements from both s and t
      s.intersection(t)	s & t	new set with elements common to s and t
      s.difference(t)	s - t	new set with elements in s but not in t
      s.symmetric_difference(t)	s ^ t	new set with elements in either s or t but not both
      s.update(t)	s |= t	return set s with elements added from t
      s.intersection_update(t)	s &= t	return set s keeping only elements also found in t
      s.difference_update(t)	s -= t	return set s after removing elements found in t
      s.symmetric_difference_update(t)	s ^= t	return set s with elements from s or t but not both

       

6. Example Using Sets

   def repeats(a):
       seen = set()
       seenAgain = set()
       for element in a:
           if (element in seen):
               seenAgain.add(element)
           seen.add(element)
       return sorted(seenAgain)
   
   print repeats([2,5,3,4,6,4,2])  # prints [2,4]

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem