Sets

7.2. Sets#

Hide code cell source

 
import sys
from pathlib import Path

current = Path.cwd()
for parent in [current, *current.parents]:
    if (parent / '_config.yml').exists():
        project_root = parent  # ← Add project root, not chapters
        break
else:
    project_root = Path.cwd().parent.parent

sys.path.insert(0, str(project_root))

from shared import thinkpython, diagram, jupyturtle
from shared.download import download

# Register as top-level modules so direct imports work in subsequent cells
sys.modules['thinkpython'] = thinkpython
sys.modules['diagram'] = diagram
sys.modules['jupyturtle'] = jupyturtle

7.2.1. What is a set#

A set is an unordered collection of unique values. Unlike lists or tuples, sets do not allow duplicates, and the elements have no guaranteed order.

Here below is an example of a set. Note that it uses curly braces just like dictionaries.

s = {1, 2, 3, 3, 2}
print(s)                ### {1, 2, 3}

{1, 2, 3}

Sets are useful when you care about membership: whether something is in a collection; rather than order or position.

The most common use cases are:

  • Removing duplicates from a list

  • Checking membership quickly

  • Comparing two collections (what’s shared, what’s different)

For sets, the four key properties that make sets different from other data structures:

  1. Unordered: Elements have no guaranteed position. There is no first or last element.

  2. Unique: Duplicates are automatically removed.

  3. Mutable: You can add and remove elements.

  4. Hashable elements only: Every element must be hashable. In practice this means immutable types: int, float, str, tuple.

### 1. Sets are unordered, so the order of elements is not guaranteed.
{3, 1, 2} == {1, 2, 3}  # True

True

### 2. Sets do not allow duplicate elements, so duplicates are automatically removed.
{1, 2, 2, 3, 3}         # {1, 2, 3}

{1, 2, 3}

### 3. Sets are mutable, so you can add or remove elements after the set is created.
s = {1, 2, 3}
s.add(4)                # works
s.remove(2)             # works
s

{1, 3, 4}

%%expect TypeError

### 4. Sets can contain only hashable (immutable) elements, so you cannot include lists or other sets as elements.
{1, "hello", (1, 2)}    # valid
{[1, 2], [3, 4]}        # TypeError

TypeError: unhashable type: 'list'

7.2.1.1. Choosing the Right Structure#

Need

Use

Ordered collection, duplicates allowed

list

Fixed data, multiple return values

tuple

Key-value lookup

dict

Unique items, membership testing

set

Hashable set (dict key, nested set)

frozenset

7.2.1.2. Hashable vs mutable#

We have seen that some data types are mutable and some are hashable. It’s now time to learn a little more about the.

  • Hashable means an object has a hash value that stays stable during its lifetime.

  • Mutable objects usually are not hashable (for example: list, dict, set).

  • Immutable objects are often hashable (for example: int, float, str, tuple), but for tuples, all nested elements must also be hashable.

  • For hash-table types: dict requires hashable keys, and set requires hashable elements.

7.2.1.2.1. Mutability#

For the property of mutability, let’s have a look over the general data structures. For in-place change methods for the common data structures, here is a comparison table. Tuple and strings are immutable, so there’s no methods available for the purpose.

Method

List

Dict

Set

Tuple

String

.append(x)

✓

.insert(i, x)

✓

.extend(iter)

✓

.update(other)

✓

✓

.remove(x)

✓

✓

.pop()

✓

✓

✓

.popitem()

✓

.add(x)

✓

.discard(x)

✓

.sort()

✓

.reverse()

✓

.setdefault(k, v)

✓

.clear()

✓

✓

✓

.intersection_update(t)

✓

.difference_update(t)

✓

.symmetric_difference_update(t)

✓

7.2.1.3. In-place set operations#

In Python, mutable methods that modify in-place typically return None. The general rule in Python is:

  • Mutates in-place → returns None

  • Returns a new object → original unchanged

These methods modify the original set instead of creating a new one:

x = {1, 2, 3}
y = {3, 4, 5}

x.update(y)                        # union in-place
print("update:", x)

x = {1, 2, 3}
x.intersection_update(y)
print("intersection_update:", x)

x = {1, 2, 3}
x.difference_update(y)
print("difference_update:", x)

x = {1, 2, 3}
x.symmetric_difference_update(y)
print("symmetric_difference_update:", x)

update: {1, 2, 3, 4, 5}
intersection_update: {3}
difference_update: {1, 2}
symmetric_difference_update: {1, 2, 4, 5}

7.2.1.3.1. Hashability#

Let us compare set, list, and dict and this time focus on hashability.

Feature

Set

List

Dict

Ordered

No

Yes

Yes (insertion order)

Duplicates

No

Yes

Keys: No, Values: Yes

Mutable

Yes

Yes

Yes

Allows only hashable elements

Yes

No

Keys only

Lookup speed

Avg O(1)

O(n)

Avg O(1)

Use case

Unique items, membership

Ordered items

Key-value pairs

In computer science, hashable means that an object can be converted into a fixed-size integer (called a hash value or hash code) via a hash function. This hash value is used to quickly locate the object in data structures like hash tables, dictionaries, and sets. For something to be hashable, it generally needs to satisfy two properties:

  • Consistency: the hash value must not change during the object’s lifetime. This is why mutable objects (like Python lists) are typically not hashable because if their contents change, their hash would need to change too, which breaks lookups.

  • Equality consistency: if two objects are considered equal (a == b), they must have the same hash value. The reverse isn’t required; two different objects can share a hash (called a collision), but equal objects must hash identically.

Hash-based data structures like hash maps and hash sets rely on hash values to place and find items in O(1) average time. If you want to use an object as a dictionary key or store it in a set, it needs to be hashable.

In summary, hashable means you can be consistently fingerprinted with a number, which is the prerequisite for being usable as a key in fast lookup structures.

key     →  hash function    →  index  →  bucket in array
"cat"   →  hash("cat")      →  42     →  array[42]

print(hash("cat"))           ### -9223372036854775808
print(hash("dog"))           ### -867955804616931492
print(hash("cat"))           ### -9223372036854775808

762818412824561485
1239000105622330567
762818412824561485

7.2.2. Creating sets#

A set is created using curly braces {} with comma-separated values, or by using the set() constructor.

Unlike lists, sets are unordered and do not allow duplicates - if you add the same value twice, it only appears once. This makes sets useful for storing unique items. One important gotcha: an empty {} creates a dict, not a set - you must use set() for an empty set.

s = {1, 2, 3, 3}       # duplicate 3 is ignored
print(s)               # {1, 2, 3}

s = set([1, 2, 2, 3])  # from a list
print(s)               # {1, 2, 3}

s = set()              # empty set
d = {}                 # this is a dict, not a set!

{1, 2, 3}
{1, 2, 3}

set elements must be hashable. Since sets use hashing internally to enforce uniqueness and enable fast lookup, all elements must be hashable. This means you can store integers, floats, strings, and tuples in a set, but not lists or dicts.

%%expect TypeError

# Valid
s = {1, "hello", (1, 2)}

# Invalid
s = {[1, 2], [3, 4]}    # TypeError: unhashable type: 'list'

TypeError: unhashable type: 'list'

Similarly, a tuple is hashable only if all of its elements are hashable.

print(hash((1, 2)))          # ok
print(hash((1, (2, 3))))     # ok

try:
    hash((1, [2, 3]))        # list inside tuple => unhashable
except TypeError as e:
    print(e)

-3550055125485641917
7267574591690527098
unhashable type: 'list'

7.2.2.1. Accessing Elements#

Sets have no indexing or positional access. Because sets are unordered, there’s no concept of “first” or “second” element, so index access makes no sense.

Compared with list and dictionary, dict is the only one with a built-in safe getter. A list requires a guard clause.

List

Dict

Set

Access

by index l[i]

by key d[key]

no direct access

Safe get

l[i] if i < len(l) else default

d.get(key, default)

val if val in s else default

Built-in safe method

none

.get()

none

 
%%expect IndexError

d = {'x': 1, 'y': 2}
d.get('z', 'not found')                 # 'not found' — no error

l = [10, 20, 30]
l[5]                                  # IndexError!   ### uncomment to see the error

IndexError: list index out of range

For list, a safe way to handle a possible out-of-range error is to use a guard clause.

l = [10, 20, 30]

result = l[5] if 5 < len(l) else None   # None — safe
print(result)                           # None

None

To work with elements in a set, you can:

Method

Example

Notes

Membership check

3 in s

True/False only, no error

Iterate

for x in s:

no guaranteed order

Convert to list

list(s)[0]

order not guaranteed

s.pop()

s.pop()

returns an arbitrary element

 
### check membership

if "apple" in s:
    print("found")

### iterate over a set
for element in s:
    print(element)

1
(1, 2)
hello

### conversion to list
l = list(s)
print(l)

[1, (1, 2), 'hello']

### s.pop() removes and returns an arbitrary element from the set. If the set is empty, it raises a KeyError.
s = {1, 2, 3}
s.pop()

1

7.2.3. Set Operations#

Sets support mathematical operations that make it easy to compare two collections. Each operation has both an operator shorthand and a method form which produce the same result:

Operation

Operator

Method

Description

Union

a | b

a.union(b)

All elements from both sets

Intersection

a & b

a.intersection(b)

Only elements common to both sets

Difference

a - b

a.difference(b)

Elements in a but not in b

Symmetric Difference

a ^ b

a.symmetric_difference(b)

Elements in either set, but not in both

 
a = {1, 2, 3}
b = {3, 4, 5}

Note that, operator forms (|, &, -, ^) require set operands. Method forms are more flexible and can take any iterable.

print(a.union([3, 4, 5]))    # works: method accepts iterable

try:
    a | [3, 4, 5]            # TypeError: right side is a list
except TypeError as e:
    print(e)

{1, 2, 3, 4, 5}
unsupported operand type(s) for |: 'set' and 'list'

7.2.3.1. Union#

All elements from both sets

a | b        # {1, 2, 3, 4, 5}
a.union(b)   # same

{1, 2, 3, 4, 5}

7.2.3.2. Intersection#

Only elements in both sets.

a & b              # {3}
a.intersection(b)  # same

{3}

7.2.3.3. Difference#

Elements in a but not in b

a - b              # {1, 2}
a.difference(b)    # same

{1, 2}

7.2.3.4. Symmetric Difference#

Elements in either set, but not both

a ^ b                       # {1, 2, 4, 5}
a.symmetric_difference(b)   # same

{1, 2, 4, 5}

### Exercise: Basic Set Operations
# 1. Create A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.
# 2. Print A | B, A & B, A - B, and A ^ B.
### Your code starts here.




### Your code ends here.

Hide code cell source

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

print("Union:", A | B)
print("Intersection:", A & B)
print("Difference A-B:", A - B)
print("Symmetric Difference:", A ^ B)

Union: {1, 2, 3, 4, 5, 6}
Intersection: {3, 4}
Difference A-B: {1, 2}
Symmetric Difference: {1, 2, 5, 6}

7.2.4. Set Methods#

Python sets have methods for adding, removing, and checking elements.

Method

Description

.add(x)

Adds a single element

.update(iterable)

Adds multiple elements

.copy()

Returns a shallow copy of the set

.remove(x)

Removes element, raises KeyError if missing

.discard(x)

Removes element, silent if missing

.pop()

Removes and returns an arbitrary element

.clear()

Empties the set

.issubset(s)

Returns True if all elements are in s

.issuperset(s)

Returns True if set contains all of s

.isdisjoint(s)

Returns True if no elements in common

7.2.4.1. Adding elements:#

  • add()

  • update(): adds multiple elements, similar to dict.update().

s = {1, 2, 3}
s.add(4)            # {1, 2, 3, 4}
s.update([5, 6])    # {1, 2, 3, 4, 5, 6}
s

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

7.2.4.2. Copy vs aliasing#

Sets are mutable, so assignment shares the same object. Use .copy() when you need an independent set.

a = {1, 2}
b = a               # alias (same object)
c = a.copy()        # separate object

a.add(3)
print("a:", a)
print("b:", b)
print("c:", c)

a: {1, 2, 3}
b: {1, 2, 3}
c: {1, 2}

7.2.4.3. Removing elements:#

  • remove()

  • discard()

  • pop()

  • clear()

s = {1, 2, 3}

s.remove(3)     # raises KeyError if not found
print(s)        # {1, 2}

s.discard(3)    # silent if not found — safer
print(s)        # {1, 2}

s.pop()         # removes and returns an arbitrary element
print(s)        # which item is removed is arbitrary

s.clear()       # empties the set
print(s)        # set()

{1, 2}
{1, 2}
{2}
set()

If you use remove() in a for loop for a set, you may run into an error because Python creates an internal iterator that tracks position inside the set. The moment you call s.remove(), the set’s structure changes and the iterator breaks and raises an error.

The solution to this problem is to iterate over a copy or just use a while loop.

%%expect RuntimeError

s = {1, 2, 3,}
for item in s:
    s.remove(item)
    print(f"Processing {item}")

Processing 1

RuntimeError: Set changed size during iteration

### iterate through copy of the set while modifying the original

for item in s.copy():   # iterate over copy
    s.remove(item)      # modify original safely
    print(f"Processing {item}")
s

Processing 2
Processing 3

set()

# process all items, consuming the set

s = {1, 2, 3}
while s:
    item = s.pop()
    print(f"Processing {item}")
# s is now empty

Processing 1
Processing 2
Processing 3

s.pop() is useful when you want to process and consume a set one element at a time, and you don’t care which element you get. This behavior is different from pop() in list and dict.

list.pop()

dict.pop()

set.pop()

Removes

by index

by key

arbitrary element

Returns

removed value

removed value

removed value

Default arg

index (default -1)

key + optional default

none

If not found

IndexError

KeyError (or default)

KeyError

Predictable?

yes (by index)

yes (by key)

no (arbitrary item)

7.2.4.4. Checking membership:#

s = {1, 2, 3}

print(3 in s)         # True
print(3 not in s)     # False

True
False

7.2.4.5. Subset & Superset:#

a = {1, 2}
b = {1, 2, 3}

a.issubset(b)    # True — all of a is in b
b.issuperset(a)  # True — b contains all of a
a.isdisjoint(b)  # False — they share elements

False

Operator equivalents for subset/superset are often used in real code:

a = {1, 2}
b = {1, 2, 3}

print(a < b)    # proper subset
print(a <= b)   # subset
print(b > a)    # proper superset
print(b >= a)   # superset
print(a <= a)   # True (same set is subset of itself)
print(a < a)    # False (not a proper subset)

True
True
True
True
True
False

### Exercise: Update and Membership Check
# 1. Start with fruits = {"apple", "banana"}.
# 2. Add "cherry" and update with ["banana", "mango"].
# 3. Remove "apple" safely.
# 4. Print whether "mango" is in fruits.
# 5. Print whether {"banana", "cherry"} is a subset of fruits.
### Your code starts here.





### Your code ends here.

Hide code cell source

 
fruits = {"apple", "banana"}
fruits.add("cherry")
fruits.update(["banana", "mango"])
fruits.discard("apple")

print("mango" in fruits)
print({"banana", "cherry"}.issubset(fruits))

True
True

7.2.5. Frozensets#

A frozenset is an immutable version of a set. Once created, elements cannot be added or removed. This is useful when, for example, you need to protect data from modification, to use set as dict key or set element, or for graph edges and combinations.

%%expect AttributeError

fs = frozenset({1, 2, 3})
fs.add(4)     # AttributeError — frozensets are immutable

AttributeError: 'frozenset' object has no attribute 'add'

7.2.5.1. Creating a frozenset#

The syntax for creating a frozenset is:

frozenset()            # empty frozenset
frozenset(iterable)    # from any iterable (list, set, string, etc.)

fs = frozenset([1, 2, 3])
print(fs)                   # frozenset({1, 2, 3})
fs = frozenset("hello")
print(fs)                   # element order may vary

frozenset({1, 2, 3})
frozenset({'l', 'e', 'o', 'h'})

7.2.5.2. Why use a frozenset?#

Because it is immutable, a frozenset is hashable, which means it can be:

  • used as a dictionary key, or

  • stored inside another set.

# As a dict key
d = {frozenset({1, 2}): "pair"}

# Inside a set
s = {frozenset({1, 2}), frozenset({3, 4})}

Feature

set

frozenset

Mutable

Yes

No

Hashable

No

Yes

Can be dict key

No

Yes

Set operations

All

Non-mutating only

7.2.6. Set Performance#

When you store a key in a dictionary or an element in a set, Python calls hash() on it to compute an integer, then uses that integer to determine where to store the value in memory. This is called a hash table.

The benefit is that lookups are usually O(1) on average: Python jumps directly to a bucket via hash instead of scanning the whole collection. In the worst case (many collisions), lookup can degrade toward O(n).

# O(n) — scans the entire list
"apple" in ["apple", "banana", "cherry"]

# Average O(1) — jumps directly via hash bucket
"apple" in {"apple", "banana", "cherry"}

True

O(n) and O(1) come from Big O notation, which describes how the speed of an operation scales with the size of the data. The full treatment of Big O comes in the Algorithms chapter, where sorting and searching will be covered.

For now, just know that:

  • Average O(1): hash-table lookups in dict/set are constant time on average, because Python uses the hash to jump to a bucket.

  • Worst-case O(n): if many keys collide into the same bucket, Python may need to scan multiple entries.

  • O(n): linear time. The operation gets slower as the collection grows. A list search is O(n) because Python checks each element one by one until it finds a match:

d = {"apple": 1, "banana": 2, "cherry": 3}
d["apple"]   # same speed whether dict has 3 or 3 million items

1

"apple" in ["apple", "banana", "cherry"]  # checks up to n items

True

In short,

  • O(1) is like looking up a word in a dictionary: you go directly to the page

  • O(n) is like finding a word in a novel: you read until you find it

You already saw this in the dictionary section, and the same idea applies here:

  • O(1) means near-constant lookup time on average (key in dict, item in set).

  • O(n) means linear time, where Python may scan through many elements (item in list).

So for membership checks, sets are usually much faster than lists as data grows.

7.2.6.1. Performance Demo#

This benchmark mirrors the dictionary example: same data size, worst-case target (n - 1), and timing for membership checks.

import time

n = 1_000_000
big_list = list(range(n))
big_set = set(range(n))
target = n - 1                  # worst case for linear list search

# O(n): list search scans until it finds target
start = time.perf_counter()     # time.perf_counter() is better for benchmarking code
result = target in big_list
list_time = time.perf_counter() - start

# Average O(1): set lookup jumps to hash bucket
start = time.perf_counter()
result = target in big_set
set_time = time.perf_counter() - start

print(f"List lookup (O(n)): {list_time:.6f} s")
print(f"Set lookup (avg O(1)): {set_time:.6f} s")
print(f"Set was ~{list_time / set_time:.0f}x faster")

List lookup (O(n)): 0.004879 s
Set lookup (avg O(1)): 0.000021 s
Set was ~231x faster

7.2.7. Set Comprehensions#

A set comprehension builds a set from an expression, using the same syntax as a list comprehension but with curly braces {}. Because the result is a set, duplicates are automatically discarded.

The syntax for creating sets is:

{expression for item in iterable}
{expression for item in iterable if condition}

# Create a set of squares
square_set = {x**2 for x in range(-3, 4)}
print("Square set:", square_set)

# Remove duplicates and transform
sentence = "the quick brown fox jumps over the lazy dog"
unique_lengths = {len(word) for word in sentence.split()}
print("Unique word lengths:", unique_lengths)

# Filter vowels
vowels = {char.lower() for char in "Hello World" if char.lower() in 'aeiou'}
print("Vowels found:", vowels)

Square set: {0, 9, 4, 1}
Unique word lengths: {3, 4, 5}
Vowels found: {'e', 'o'}

### Exercise: Set Comprehension Practice
# 1. From nums = [1, 2, 2, 3, 4, 4, 5], build a set of squared values.
# 2. From text = "apple banana apple cherry", build a set of unique word lengths.
# 3. Print both sets.
### Your code starts here.




### Your code ends here.

Hide code cell source

 
nums = [1, 2, 2, 3, 4, 4, 5]
squares = {n**2 for n in nums}

text = "apple banana apple cherry"
lengths = {len(word) for word in text.split()}

print("Squares:", squares)
print("Unique lengths:", lengths)

Squares: {1, 4, 9, 16, 25}
Unique lengths: {5, 6}

7.2.7.1. Comparing with dict Comprehension#

# Set comprehension — curly braces, no colon
{x**2 for x in range(5)}

# Dict comprehension — curly braces WITH colon
{x: x**2 for x in range(5)}

{0: 0, 1: 1, 2: 4, 3: 9, 4: 16}
Contents