Programming Python, Second Edition

Implementing Sets

Another commonly used data structure is the set, a collection of objects that support operations such as:

Intersection

Make a new set with all items in common.

Union

Make a new set with all items in either operand.

Membership

Test if an item exists in a set.

And there are others, depending on the intended use. Sets come in handy for dealing with more abstract group combinations. For instance, given a set of engineers and a set of writers, you can pick out individuals who do both activities by intersecting the two sets. A union of such sets would contain either type of individual, but only include any given individual once.

Python lists, tuples, and strings come close to the notion of a set: the in operator tests membership, for iterates, etc. Here, we add operations not directly supported by Python sequences. The idea is that we’re extending built-in types for unique requirements.

Set Functions

As before, let’s first start out with a function-based set manager. But this time, instead of managing a shared set object in a module, let’s define functions to implement set operations on passed-in Python sequences (see Example 17-8).

Example 17-8. PP2E\Dstruct\Basic\inter.py

def intersect(seq1, seq2): res = [] # start with an empty list for x in seq1: # scan the first sequence if x in seq2: res.append(x) # add common items to the end return res def union(seq1, seq2): res = list(seq1) # make a copy of seq1 for x in seq2: # add new items in seq2 if not x in res: res.append(x) ...