Sets
One more built-in Python container type
Set literals are enclosed in braces
Duplicate elements are removed on construction
Sets are unordered, just like dictionary entries
s = {3, 2, 1, 4, 4}
{1, 2, 3, 4}
s.union({1, 5}) = {1, 2, 3, 4, 5}
return all elements either in set or in other set
s.intersection({6, 5, 4, 3})
return set of all elements that are in both set
Implementing Sets
What we should be able to do with set:
Membership testing: Is value an element of a set?
Union: return set with all elements in set1 or set2
Intersection: return set with any elements in both set1 and set2
Adjunction: return set with all elements in s and a value v
Never mutate input sets, create new output set
Sets as Unordered Sequences
Proposal 1: A set is represented by recursive list that contains no duplicate item
def empty(s):
return s is Rlist.empty
def set_contains(s, v):
"""Return true if set s contains value v as an element.
>>> set_contains(s, 2)
True
>>> set_contains(s, 5)
False
"""
if empty(s):
return False
elif s.first == v:
return True
else:
return set_contains(s.rest, v)
def adjoin_set(s, v):
"""Return a set containing all elements of s and element v.
>>> t = adjoin_set(s, 4)
>>> t
Rlist(4, Rlist(1, Rlist(2, Rlist(3))))
""" if set_contains(s, v):
return s
else:
return Rlist(v, s)
def intersect_set(set1, set2):
"""Return a set containing all elements common to set1 and set2.
>>> t = adjoin_set(s, 4)
>>> intersect_set(t, map_rlist(s, lambda x: x*x))
Rlist(4, Rlist(1))
"""
in_set2 = lambda v: set_contains(set2, v)
return filter_rlist(set1, in_set2)
def union_set(set1, set2):
"""Return a set containing all elements either in set1 or set2.
>>> t = adjoin_set(s, 4)
>>> union_set(t, s)
Rlist(4, Rlist(1, Rlist(2, Rlist(3))))
"""
not_in_set2 = lambda v: not set_contains(set2, v)
set1_not_set2 = filter_rlist(set1, not_in_set2)
return extend_rlist(set1_not_set2, set2)
Review: Order of Growth
For set operation that takes "linear" time, we say that
n: size of the set
R(n): number of steps required to perform operation
R(n) = Theta(n)
positive constant k1 and k2 such that
k1 * n <= R(n) <= k2 * n
for sufficiently large values of n
Order of growth: Theta(N^2)
Sets as Ordered Sequences
Proposal 2: A set is represented by a recursive list with unique elements ordered
from least to greatest
Order

More
Less