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

 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