8: Set

Section 8.1: Operations on sets

with other sets

#Add and Removes = {1,2,3}

Set operations return new sets, but have the corresponding in-place versions:

Intersection

a.intersection(b) returns a new set with elements present in both a and b

>>>a.intersection(b) {3, 4}

Union

a.union(b) returns a new set with elements present in either a and b

>>>a.union(b) {1, 2, 3, 4, 5}

Difference

a.difference(b) returns a new set with elements present in a but not in b

>>>a.difference(b) {1, 2}

>>>b.difference(a)

{5}

Symmetric Difference

a.symmetric_difference(b) returns a new set with elements present in either a or b but not in both

>>>a.symmetric_difference(b) {1, 2, 5}

>>>b.symmetric_difference(a) {1, 2, 5}

NOTE: a.symmetric_difference(b) == b.symmetric_difference(a)

Subset and superset

c.issubset(a) tests whether each element of c is in a. a.issuperset(c) tests whether each element of c is in a.

>>>c = {1, 2}

>>>c.issubset(a)

True

>>>a.issuperset(c)

True

The latter operations have equivalent operators as shown below:

Disjoint sets

Sets a and d are disjoint if no element in a is also in d and vice versa.

>>>d = {5, 6}

>>>a.isdisjoint(b) # {2, 3, 4} are in both sets False

>>>a.isdisjoint(d)

True

#This is an equivalent check, but less efficient

>>> len(a & d) == 0 True

#This is even less efficient

>>>a & d == set()

True

Testing membership

The builtin in keyword searches for occurances

>>>1 in a

True

>>>6 in a False

Length

The builtin len() function returns the number of elements in the set

>>>len(a)

4

>>>len(b)

3

Section 8.5: Sets versus multisets

Sets are unordered collections of distinct elements. But sometimes we want to work with unordered collections of elements that are not necessarily distinct and keep track of the elements’ multiplicities.

Consider this example:

>>>setA = {‘a’,‘b’,‘b’,‘c’}

>>>setA

set([‘a’, ‘c’, ‘b’])

By saving the strings ‘a’, ‘b’, ‘b’, ‘c’ into a set data structure we’ve lost the information on the fact that ‘b’ occurs twice. Of course saving the elements to a list would retain this information

>>>listA = [‘a’,‘b’,‘b’,‘c’]

>>>listA

[‘a’, ‘b’, ‘b’, ‘c’]

but a list data structure introduces an extra unneeded ordering that will slow down our computations.

For implementing multisets Python provides the Counter class from the collections module (starting from version 2.7):

Python 2.x Version ≥ 2.7

>>>from collections import Counter

>>>counterA = Counter([‘a’,‘b’,‘b’,‘c’])

>>>counterA

Counter({‘b’: 2, ‘a’: 1, ‘c’: 1})

Counter is a dictionary where where elements are stored as dictionary keys and their counts are stored as dictionary values. And as all dictionaries, it is an unordered collection.