Sets

4. Data Structures: Sets

Sets

The #\color{#4271ae} {\mathtt{\text{set}}}# object is a peculiar one. You can think of a #\color{#4271ae} {\mathtt{\text{set}}}# as a group of arbitrary objects with no particular order. Most functionality of the #\color{#4271ae} {\mathtt{\text{set}}}# object tries to emulate principles of the mathematical field of set theory. Sets are mutable, but can only contain immutable objects. A #\color{#4271ae} {\mathtt{\text{set}}}# is most commonly defined by specifying a comma-separated sequence inside curly brackets.

Declaring a set

#\mathtt{\{}\textit{object}_\textit{0},\textit{object}_\textit{1}, \dots, \textit{object}_\textit{n}\mathtt{\}}#

#\color{#4271ae} {\mathtt{set}}\mathtt{(}\textit{iterable}\mathtt{)}#

The objects that make up a #\color{#4271ae} {\mathtt{\text{set}}}# can be any immutable Python object. The order in which you specify objects within the curly brackets is not necessarily preserved when the code is executed. Another property of sets is that they can only store unique elements, when you define duplicate elements, any subsequent duplicate instance is simply ignored.

>>> {2, 3, 1}

{1, 2, 3}

>>> set("Hello, world!")

{' ', '!', ',', 'H', 'd', 'e', 'l', 'o', 'r', 'w'}

When a #\color{#4271ae} {\mathtt{\text{set}}}# is displayed, its elements are sometimes still shown in ascending order. This does not mean that this is also how the #\color{#4271ae} {\mathtt{\text{set}}}# is stored in memory. If we iterate over the set in the second example the characters are returned in a different order than initially displayed.

>>> [char for char in set("Hello, world!")]

[',', 'H', 'l', 'e', 'r', 'o', ' ', 'w', '!', 'd']

The actual ordering of a #\color{#4271ae} {\mathtt{\text{set}}}# is dependent on a lot of factors and can even change between different runs of a program. Therefore, a #\color{#4271ae} {\mathtt{\text{set}}}# is commonly defined as an unordered collection of objects.

Set theory is the branch of mathematical logic that studies sets. Set theory defines a lot of relations between sets. Python also enables you to test for these relations between its #\color{#4271ae} {\mathtt{\text{set}}}# objects.

Set theory methods

Python supports the most common operations of set theory between two #\color{#4271ae} {\mathtt{\text{set}}}# objects; the union, the intersection, the difference, and the symmetric difference between two sets are all supported, both as operator and method.

>>> A = {1, 2, 3}
>>> B = {3, 4, 5}
>>> C = {5, 6, 7}

Name	Operator	Method	Result
Union	#\mathtt{\text{A}\color{#3e999f} {\text{ \| }}\text{B}}#	#\mathtt{\text{A.}\color{#4271ae} {\text{union}}\text{(B)}}#	#\mathtt{\text{\{}\color{#F5871F}{\text{1}}\text{, }\color{#F5871F}{\text{2}}\text{, }\color{#F5871F}{\text{3}}\text{, }\color{#F5871F}{\text{4}}\text{, }\color{#F5871F}{\text{5}}\text{\}}}#
Intersection	#\mathtt{\text{A}\color{#3e999f} {\text{ & }}\text{B}}#	#\mathtt{\text{A.}\color{#4271ae} {\text{intersection}}\text{(B)}}#	#\mathtt{\text{\{}\color{#F5871F}{\text{3}}\text{\}}}#
Difference	#\mathtt{\text{A}\color{#3e999f} {\text{ - }}\text{B}}#	#\mathtt{\text{A.}\color{#4271ae} {\text{difference}}\text{(B)}}#	#\mathtt{\text{\{}\color{#F5871F}{\text{1}}\text{, }\color{#F5871F}{\text{2}}\text{\}}}#
Symmetric Difference	#\mathtt{\text{A}\color{#3e999f} {\text{ ^ }}\text{B}}#	#\mathtt{\text{A.}\color{#4271ae} {\text{symmetric_difference}}\text{(B)}}#	#\mathtt{\text{\{}\color{#F5871F}{\text{1}}\text{, }\color{#F5871F}{\text{2}}\text{, }\color{#F5871F}{\text{4}}\text{, }\color{#F5871F}{\text{5}}\text{\}}}#

Multiple sets

When you want to perform a set operation with more than one set, you can simply chain operators.

>>> A | B | C

{1, 2, 3, 4, 5, 6, 7}

if you want to do the same, but using methods, you can specify more than one set as argument for the desired method.

>>> A.union(B, C)

{1, 2, 3, 4, 5, 6, 7}

Set operations are left-associative, they are evaluated from left to right.

Shorthands

Note that the set operation methods we have discussed return a new #\color{#4271ae} {\mathtt{\text{set}}}# object. Since sets are mutable, we are able to change them in-place. We could use the syntax #\mathtt{\text{A}\text{ = }\text{A}\text{ | }\text{B}}#, for which the shorthand #\mathtt{\text{|=}}# exists, or one of the methods intended for updating sets in place.

Syntax	Shorthand	Method
#\mathtt{\text{A}\color{#3e999f}{\text{ = }}\text{A}\color{#3e999f}{\text{ \| }}\text{B}}#	#\mathtt{\text{A}\color{#3e999f}{\text{ \|= }}\text{B}}#	#\mathtt{\text{A.}\color{#4271ae}{\text{update}}\text{(B)}}#
#\mathtt{\text{A}\color{#3e999f}{\text{ = }}\text{A}\color{#3e999f}{\text{ & }}\text{B}}#	#\mathtt{\text{A}\color{#3e999f}{\text{ &= }}\text{B}}#	#\mathtt{\text{A.}\color{#4271ae}{\text{intersection_update}}\text{(B)}}#
#\mathtt{\text{A}\color{#3e999f}{\text{ = }}\text{A}\color{#3e999f}{\text{ - }}\text{B}}#	#\mathtt{\text{A}\color{#3e999f}{\text{ -= }}\text{B}}#	#\mathtt{\text{A.}\color{#4271ae}{\text{difference_update}}\text{(B)}}#
#\mathtt{\text{A}\color{#3e999f}{\text{ ^ }}\text{A}\color{#3e999f}{\text{ \| }}\text{B}}#	#\mathtt{\text{A}\color{#3e999f}{\text{ ^= }}\text{B}}#	#\mathtt{\text{A.}\color{#4271ae}{\text{symmetric_difference_update}}\text{(B)}}#

As you may remember, this syntax, and in extension, these shorthands, are generally used in loops.

>>> new = set()
>>> for s in A, B, C:
new |= s
>>> new

{1, 2, 3, 4, 5, 6, 7}

Comparisons

The comparison operators for sets provide very different functionality than we've seen thus far. They determine whether a set is a sub- or superset of another set. A set is considered a subset of another set if it only contains elements of the other set. A set is a superset of another set when it contains all elements of the other set. The difference between a normal sub- or superset and a proper one is that identical sets are not proper sub- or supersets.

Name	Operator	Method	Returns
Is disjoint		#\mathtt{\text{A.}\color{#4271ae}{\text{isdisjoint}}\text{(B)}}#	Returns #\mathtt{\color{#F5871F}{\text{True}}}# if #\mathtt{\text{A}}# and #\mathtt{\text{B}}# have no elements in common.
Is subset	#\mathtt{\text{A}\color{#3e999f}{\text{ <= }}\text{B}}#	#\mathtt{\text{A.}\color{#4271ae}{\text{issubset}}\text{(B)}}#	Returns #\mathtt{\color{#F5871F}{\text{True}}}# if #\mathtt{\text{A}}# is a subset of #\mathtt{\text{B}}#.
Is superset	#\mathtt{\text{A}\color{#3e999f}{\text{ >= }}\text{B}}#	#\mathtt{\text{A.}\color{#4271ae}{\text{issuperset}}\text{(B)}}#	Returns #\mathtt{\color{#F5871F}{\text{True}}}# if #\mathtt{\text{A}}# is a superset of #\mathtt{\text{B}}#.
Is proper subset	#\mathtt{\text{A}\color{#3e999f}{\text{ < }}\text{B}}#		Returns #\mathtt{\color{#F5871F}{\text{True}}}# if #\mathtt{\text{A}}# is a proper subset of #\mathtt{\text{B}}#.
Is proper superset	#\mathtt{\text{A}\color{#3e999f}{\text{ > }}\text{B}}#		Returns #\mathtt{\color{#F5871F}{\text{True}}}# if #\mathtt{\text{A}}# is a proper superset of #\mathtt{\text{B}}#.

Note, that you can only test whether sets are disjoint using a method, and only operators to determine whether a set is a proper sub- or superset. A few additional examples of set comparisons:

>>> A <= {1, 2, 3, 4}

True

>>> A < {1, 2, 3}

False

>>> A.isdisjoint(B)

False

Because sets are an unordered collection of objects, they do not support indexing or slicing. They do still support methods that add and remove elements. These differ from the methods explained above in that arguments and returned values can also be different objects than sets. They also support the same keywords as tuples.

Other set functionality

Sets only support one straight-forward function for adding elements; the #\mathtt{\color{#4271ae} {\text{add}}\text{()}}# function allows you to add objects to the set as individual elements.

>>> s = {1, 2}
>>> s.add(3)
>>> s

{1, 2, 3}

>>> s.add((1, 2, 3))

{(1, 2, 3), 1, 2, 3}

Sets support three functions for the removal of elements. These functions are #\mathtt{\color{#4271ae} {\text{pop}}\text{()}}#, which removes and returns an arbitrary member of the set, #\mathtt{\color{#4271ae} {\text{remove}}\text{()}}# and #\mathtt{\color{#4271ae} {\text{discard}}\text{()}}#, which both remove the member given as an argument. However, #\mathtt{\color{#4271ae} {\text{remove}}\text{()}}# returns an error when the member can't be found, while #\mathtt{\color{#4271ae} {\text{discard}}\text{()}}# does not.

>>> s.pop()

>>> s.remove((1, 2, 3))

{2, 3}

Sets also support the #\mathtt{\color{#4271ae} {\text{clear}}\text{()}}# method to remove all members of the #\mathtt{\color{#4271ae} {\text{set}}}#.

Keywords

Like the other iterables, sets also support testing for membership of objects using the #\color{#8959A8}{\mathtt{\text{in}}}# keyword.

>>> 3 in s

True

They also support the simple syntax for looping over iterables. Note that the order in which elements are yielded can be surprising.

>>> for member in s:
print(member)

2
3

They also support the comprehension syntax for quick initialisiation.

>>> {member for member in range(10)}

{1, 2, 3, 4, 5, 6, 7, 8, 9}