Sets

Notes

Mathematical sets

Begin with a review of the mathematical concept of a set:

A set is a collection of objects or numbers that are specified in some well-defined manner. Each item in the set is called an element.

Various properties of sets can be enumerated, such as notation for constructing sets, how we determine if two sets are equal, set operations, etc.

Computer science sets

Sets are data structures that correspond to the mathematical set object.

Sets are defined by their chief characteristic, which is that sets cannot contain duplicates. They are not indexed, and items are accessed directly. The set data structure works similar to the map data structure with its key-value lookup, but the set has no keys - the values are their own keys.

The Set class defines an abstract data type. This abstract data type must provide the following five public methods:

• S.add(e) - add element e to set
• S.discard(e) - remove e from set
• e in S - returns true if e is in S
• len(S) or S.size() - size of set
• iter(S) or S.iterator() - get an iterator over set elements

To see more details about the Set ADT, see Sets/ADT.

Other utility methods include remove (passing a specific element) and pop (remove one element), as well as the usual size, check if empty, clear.

Finally, there are several operations that need to be redefined for sets. These include both set operations and algebraic operations (e.g., equality).

Operations:

• Equals - returns true if two sets have identical contents
• Subset / proper subset - returns true if set S is proper subset of set T. This is convenient to implement using the <= or < operators
• Superset / proper superset - returns true if set S is proper superset of set T. Convenient to implement using >= or > operators.
• Disjoint - returns true if S and T contain no common elements

Other set operations:

• Union operation - the union of two sets S and T consists of all elements that are in S or T or both
• Intersection operation - the intersection of two sets S and T consists of all elements that are in both S and T
• Symmetric difference - consists of all elements that are in S but not T, or in T but not S
• Remove all - if any items in the current set are in the passed set, remove them
• Retain all - if any items in the current set are not contained in the passed set, remove them