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

1. Quick Example
2. Creating Sets
3. Properties of Sets
   1. Sets are Unordered
   2. Elements are Unique
   3. Elements Must Be Immutable
   4. Sets are Very Efficient
4. Set Operations
5. Some Worked Examples Using Sets

1. Quick Example
   
   s = set([2,3,5]) print(3 in s) # prints True print(4 in s) # prints False for x in range(7): if (x not in s): print(x) # prints 0 1 4 6


2. Creating Sets
   
   • Create an empty set
     s = set() print(s) # prints set()
   
   
   • Create a set from a list
     s = set(["cat", "cow", "dog"]) print(s) # prints {'cow', 'dog', 'cat'}
   
   
   • Create a set from any iterable object
     s = set("wahoo") print(s) # surprised?
   
   
   • Create a statically-allocated set
     s = { 2, 3, 5 } print(s) # prints { 2, 3, 5 }
   
   
   • Caution: { } is not an empty set!
     s = { } print(type(s) == set) # False! print(type(s)) # This is a dict (we'll learn about those soon)


3. Properties of Sets
   1. Sets are Unordered
      
      s = set([2,4,8]) print(s) # prints {8, 2, 4} in standard Python (though not in brython) for element in s: # prints 8, 2, 4 print(element)
   
   
   2. Elements are Unique
      
      s = set([2,2,2]) print(s) # prints {2} print(len(s)) # prints 1
   
   
   3. Elements Must Be Immutable
      
      a = ["lists", "are", "mutable"] s = set([a]) # TypeError: unhashable type: 'list' print(s)
      
      Another example:
      s1 = set(["sets", "are", "mutable", "too"]) s2 = set([s1]) # TypeError: unhashable type: 'set' print(s)
   
   
   4. Sets are Very Efficient
      
      # 0. Preliminaries import time n = 1000 # 1. Create a list [2,4,6,...,n] then check for membership # among [1,2,3,...,n] in that list. # don't count the list creation in the timing a = list(range(2,n+1,2)) print("Using a list... ", end="") start = time.time() count = 0 for x in range(n+1): if x in a: count += 1 end = time.time() elapsed1 = end - start print("count=", count," and time = %0.4f seconds" % elapsed1) # 2. Repeat, using a set print("Using a set.... ", end="") start = time.time() s = set(a) count = 0 for x in range(n+1): if x in s: count += 1 end = time.time() elapsed2 = end - start print("count=", count," and time = %0.4f seconds" % elapsed2) print("With n=%d, sets ran about %0.1f times faster than lists!" % (n, elapsed1/elapsed2)) print("Try a larger n to see an even greater savings!")


4. Set Operations
   Set operations are provided via operators, functions, and methods in Python as follows:
   
   
   1. Operations on a set
      
      

      Operation	Result	Example
      len(s)	cardinality (size) of set s	s = { 2, 3, 2, 4, 3 } print(len(s))
      s.copy()	new set with a shallow copy of s	s = { 1, 2, 3 } t = s.copy() s.add(4) print(s) print(t)
      s.pop()	remove and return an arbitrary element from s; raises KeyError if empty	s = { 2, 4, 8 } print(s.pop()) # unpredictable! print(s)
      s.clear()	remove all elements from set s	s = { 1, 2, 3 } s.clear() print(s, len(s))

   
   
   2. Operations on a set and an element
      
      

      Operation	Result	Example
      x in s	test x for membership in s	s = { 1, 2, 3 } print(0 in s) print(1 in s)
      x not in s	test x for non-membership in s	s = { 1, 2, 3 } print(0 not in s) print(1 not in s)
      s.add(x)	add element x to set s	s = { 1, 2, 3 } print(s, 4 in s) s.add(4) print(s, 4 in s)
      s.remove(x)	remove x from set s; raises KeyError if not present	s = { 1, 2, 3 } print(s, 3 in s) s.remove(3) print(s, 3 in s) s.remove(3) # crashes
      s.discard(x)	removes x from set s if present	s = { 1, 2, 3 } print(s, 3 in s) s.discard(3) print(s, 3 in s) s.discard(3) # does not crash! print(s, 3 in s)

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

      Operation	Equivalent	Result	Example
      s.issubset(t)	s <= t	test whether every element in s is in t	print({1,2} <= {1}, {1,2}.issubset({1})) print({1,2} <= {1,2}, {1,2}.issubset({1,2})) print({1,2} <= {1,2,3}, {1,2}.issubset({1,2,3}))
      s.issuperset(t)	s >= t	test whether every element in t is in s	print({1,2} >= {1}, {1,2}.issuperset({1})) print({1,2} >= {1,2}, {1,2}.issuperset({1,2})) print({1,2} >= {1,2,3}, {1,2}.issuperset({1,2,3}))
      s.union(t)	s | t	new set with elements from both s and t	print({1,2} | {1}, {1,2}.union({1})) print({1,2} | {1,3}, {1,2}.union({1,3})) s = {1,2} t = s | {1,3} print(s, t)
      s.intersection(t)	s & t	new set with elements common to s and t	print({1,2} & {1}, {1,2}.intersection({1})) print({1,2} & {1,3}, {1,2}.intersection({1,3})) s = {1,2} t = s & {1,3} print(s, t)
      s.difference(t)	s - t	new set with elements in s but not in t	print({1,2} - {1}, {1,2}.difference({1})) print({1,2} - {1,3}, {1,2}.difference({1,3})) s = {1,2} t = s - {1,3} print(s, t)
      s.symmetric_difference(t)	s ^ t	new set with elements in either s or t but not both	print({1,2} ^ {1}, {1,2}.symmetric_difference({1})) print({1,2} ^ {1,3}, {1,2}.symmetric_difference({1,3})) s = {1,2} t = s ^ {1,3} print(s, t)
      s.update(t)	s |= t	modify s adding all elements found in t	s = {1,2} t = {1,3} u = {2,3} s.update(u) t |= u print(s, t, u)
      s.intersection_update(t)	s &= t	modify s keeping only elements also found in t	s = {1,2} t = {1,3} u = {2,3} s.intersection_update(u) t &= u print(s, t, u)
      s.difference_update(t)	s -= t	modify s removing all elements found in t	s = {1,2} t = {1,3} u = {2,3} s.difference_update(u) t -= u print(s, t, u)
      s.symmetric_difference_update(t)	s ^= t	modify s keeping elements from s or t but not both	s = {1,2} t = {1,3} u = {2,3} s.symmetric_difference_update(u) t ^= u print(s, t, u)



5. Some Worked Examples Using Sets
   
   • isPermutation(L)
   • repeats(L)