Python Sets & Set Algebra

A set (set) Mutable is an unordered collection of unique items. Sets are the right tool for removing duplicates, testing membership quickly, and comparing groups of values with operations borrowed from mathematics: union, intersection, and difference.

At a Glance

Task	Syntax	Example
Create	{...}, set(iterable)	set([1, 2, 2, 3]) gives {1, 2, 3}
Create an empty set	set()	{} is a dict, not a set
Add one	s.add(x)	s.add(4)
Add many	s.update(iterable)	s.update([4, 5])
Remove safely	s.discard(x)	No error if x is missing
Test membership	x in s	3 in {1, 2, 3} gives True
Union	a | b	Everything in either set
Intersection	a & b	Only what both share
Difference	a - b	In a but not in b
Remove duplicates	set(items)	set([1, 1, 2]) gives {1, 2}

---

Creating Sets

creating_sets.py

populated = {1, 2, 3}                # Literal
empty = set()                        # Empty set
unique = {1, 2, 2, 3, 3, 3}          # {1, 2, 3}, duplicates are dropped
from_list = set([3, 1, 2, 3])        # {1, 2, 3}
chars = set('hello')                 # {'h', 'e', 'l', 'o'}, one entry per distinct letter
squares = {n ** 2 for n in range(5)} # Set comprehension: {0, 1, 4, 9, 16}

Danger

{} creates an empty dictionary, not an empty set. Always use set() for an empty set.

print(type({}))      # <class 'dict'>
print(type(set()))   # <class 'set'>

Elements Must Be Hashable Rule

Set elements must be hashable, which in practice means immutable: numbers, strings, booleans, None, and tuples of hashable items. Lists, dictionaries, and other sets cannot be elements.

hashability.py

ok = {1, 'two', (3, 4)}

bad = {[1, 2]}          # TypeError: unhashable type: 'list'
bad = {{1, 2}, {3}}     # TypeError: unhashable type: 'set'

Equal values count as the same element, so {1, 1.0, True} collapses to {1}.

---

Basic Operations

Sets have no order, so they do not support indexing or slicing. Iteration order is arbitrary and should never be relied on.

basic_operations.py

colors = {'red', 'green', 'blue'}

print(len(colors))          # 3
print('red' in colors)      # True, an O(1) hash lookup
print(colors[0])            # TypeError: 'set' object is not subscriptable

for color in sorted(colors):    # sorted() returns a list in a predictable order
    print(color)                # blue, green, red

print(min({3, 1, 2}), max({3, 1, 2}), sum({3, 1, 2}))   # 1 3 6

---

Adding and Removing Elements

Method	Behavior	If the item is missing
.add(x)	Inserts x	Not applicable. Duplicates are silently ignored
.update(*iterables)	Adds every item from one or more iterables	Not applicable
.remove(x)	Deletes x	Raises KeyError
.discard(x)	Deletes x	Does nothing
.pop()	Removes and returns an arbitrary item	Raises KeyError if the set is empty
.clear()	Removes everything	Not applicable

set_mutation.py

my_set = {1, 2, 3, 4, 5}

my_set.add(6)                 # {1, 2, 3, 4, 5, 6}
my_set.add(5)                 # No change, 5 is already present
my_set.update([6, 7])         # {1, 2, 3, 4, 5, 6, 7}
my_set.update([8], (9, 10))   # Several iterables at once

my_set.discard(99)            # Safe, no error
my_set.remove(99)             # KeyError: 99

evicted = my_set.pop()        # Removes some element, you cannot predict which
set().pop()                   # KeyError: 'pop from an empty set'

Caution

.add() inserts its argument as one element, while .update() unpacks an iterable into its items. With strings the difference is easy to miss:

s = set()
s.add('ab')       # {'ab'}
s.update('cd')    # {'ab', 'c', 'd'}

---

Set Operations

Set operations return a new set and leave the originals untouched.

Operation	Operator	Method	Result
Union	a | b	a.union(b)	Items in a, b, or both
Intersection	a & b	a.intersection(b)	Items in both
Difference	a - b	a.difference(b)	Items in a that are not in b
Symmetric difference	a ^ b	a.symmetric_difference(b)	Items in one set but not both

set_algebra.py

s1 = {1, 2, 3, 4, 5}
s2 = {2, 3, 4, 6}

print(s1 | s2)    # {1, 2, 3, 4, 5, 6}
print(s1 & s2)    # {2, 3, 4}
print(s1 - s2)    # {1, 5}
print(s1 ^ s2)    # {1, 5, 6}
print(s2 - s1)    # {6}, difference is not symmetric

Operators vs. Methods

Operators

{1, 2} | {3}        # {1, 2, 3}
{1, 2} | [3]        # TypeError: unsupported operand type(s) for |: 'set' and 'list'

Concise, but both sides must be sets.

Methods

{1, 2}.union([3])                  # {1, 2, 3}, any iterable is accepted
{1, 2, 3}.intersection([2, 3, 9])  # {2, 3}
set.union({1}, {2}, {3})           # {1, 2, 3}, several sets at once

More flexible, and the only choice when an argument is a list, tuple, or range.

In-Place Versions

Each operation has a version that modifies the set itself.

Operator	Method	Effect
s |= t	s.update(t)	Adds every item of t
s &= t	s.intersection_update(t)	Keeps only items also in t
s -= t	s.difference_update(t)	Removes items found in t
s ^= t	s.symmetric_difference_update(t)	Keeps items in exactly one of the two

in_place_operations.py

s1 = {1, 2, 3, 4, 5}
s2 = {2, 3, 4, 6}

s1 -= s2                              # s1 is now {1, 5}
s2.intersection_update([3, 4, 10])    # s2 is now {3, 4}, methods accept a list

---

Comparing Sets

Check	Operator	Method	True when…
Equal	a == b	n/a	They have exactly the same elements
Subset	a <= b	a.issubset(b)	Every item of a is in b
Proper subset	a < b	n/a	a is a subset of b and not equal to it
Superset	a >= b	a.issuperset(b)	a contains every item of b
Disjoint	n/a	a.isdisjoint(b)	They share no items

set_comparisons.py

print({1, 2} <= {1, 2, 3})      # True
print({1, 2} <= {1, 2})         # True, a set is a subset of itself
print({1, 2} < {1, 2})          # False, but not a proper subset
print({1, 2, 3} >= {2})         # True
print({1, 2}.isdisjoint({3}))   # True
print({1, 2, 3} == {3, 2, 1})   # True, order is irrelevant

---

Practical Patterns

Removing Duplicates

deduplication.py

raw_ids = [101, 102, 102, 105, 108, 108, 110]

unique_ids = set(raw_ids)                # {101, 102, 105, 108, 110}, order is NOT preserved
ordered = list(dict.fromkeys(raw_ids))   # [101, 102, 105, 108, 110], order IS preserved

Fast Membership Checks

Looking up an item in a list scans it from the start (O(n)), while a set jumps straight to it (O(1) on average). When you test membership repeatedly against a large collection, convert it to a set once.

fast_membership.py

allowed_users = {101, 105, 108}      # Hash table lookup

def is_authorized(user_id):
    return user_id in allowed_users  # O(1), versus O(n) for a list

Comparing Two Groups

Set algebra turns “what is missing?” questions into one-liners.

comparing_groups.py

required = {'read', 'write'}
granted = {'read', 'comment'}

print(required - granted)    # {'write'}, what is still missing
print(granted - required)    # {'comment'}, what is extra
print(required & granted)    # {'read'}, what matches
print(required <= granted)   # False, not every requirement is met

Finding Duplicates

find_duplicates.py

items = ['a', 'b', 'a', 'c', 'b']

seen = set()
duplicates = set()

for item in items:
    if item in seen:
        duplicates.add(item)
    else:
        seen.add(item)

print(duplicates)   # {'a', 'b'}

Set Comprehensions

set_comprehension.py

raw_ids = [101, 102, 102, 105, 108, 108, 110]

even_squares = {x ** 2 for x in raw_ids if x % 2 == 0}
print(even_squares)   # {10404, 11664, 12100}

---

Frozen Sets

A frozenset is an immutable set. Because it is hashable, it can be used as a dictionary key or as an element of another set, which regular sets cannot.

frozenset.py

fs = frozenset([1, 2, 3])

fs.add(4)                               # AttributeError: 'frozenset' object has no attribute 'add'
print(fs | {4})                         # frozenset({1, 2, 3, 4}), operations still work

groups = {frozenset({1, 2}): 'pair'}    # Usable as a dictionary key
nested = {frozenset({1, 2}), frozenset({3})}   # A set of sets

---

Copying Sets

copying_sets.py

a = {1, 2, 3}

b = a                # Not a copy: both names refer to the same set
c = a.copy()         # A real copy (also: set(a))

b.add(4)
print(a)             # {1, 2, 3, 4}, changed through the alias
print(c)             # {1, 2, 3}, unaffected

Because set elements must be immutable, a shallow copy of a set is effectively fully independent. No deep copy is needed.

---

Changing a Set While Looping

Adding or removing elements while iterating over a set raises a RuntimeError. Build a new set instead.

mutation_during_iteration.py

numbers = {1, 2, 3, 4}

for n in numbers:
    if n % 2 == 0:
        numbers.remove(n)    # RuntimeError: Set changed size during iteration

numbers = {n for n in numbers if n % 2 != 0}   # Correct: {1, 3}

---

Time Complexity

Sets are built on hash tables. O(1) means the cost stays constant no matter how many elements the set holds. These figures are average-case. Heavy hash collisions can degrade individual operations toward O(n), though this is rare in practice.

Operation	Complexity	Note
x in s	O(1) Fast	Average case
s.add(x), s.remove(x), s.discard(x), s.pop()	O(1) Fast	Average case
len(s)	O(1) Fast	Stored size
a | b, a ^ b	O(len(a) + len(b)) Linear	Builds a new set
a & b	O(min(len(a), len(b))) Linear	Average case
a - b	O(len(a)) Linear	Every item of a is checked against b
a <= b	O(len(a)) Linear	Each item of a is looked up in b
s.copy(), looping over s	O(n) Linear	Touches every item

---

When to Reach for a Set

1. You need unique items. Pass any iterable through set() to drop duplicates in O(n) time. If order matters, use dict.fromkeys() instead.

2. You test membership repeatedly. Convert the collection from a list to a set once, then enjoy O(1) lookups.

3. You compare groups. Use &, |, -, and ^ instead of nested loops.

4. You need an immutable or hashable group. Use frozenset, for example as a dictionary key.

---

Common Mistakes

Mistake	Problem	Fix
empty = {}	Creates a dictionary	empty = set()
s[0]	TypeError, sets are not indexable	sorted(s)[0], or use a list or tuple
{[1, 2], [3]}	TypeError, lists are unhashable	Use tuples: {(1, 2), (3,)}
s.remove(x) on a missing item	KeyError	s.discard(x)
Relying on iteration order	Order is arbitrary	sorted(s), or use a list or dict
{1, 2} | [3]	TypeError, operators need two sets	{1, 2}.union([3])
s.add('ab') expecting two items	Adds the single string 'ab'	s.update('ab')
set('hello') expecting {'hello'}	Splits into characters	{'hello'}
set(items) when order matters	Order is lost	list(dict.fromkeys(items))
Removing items inside a for loop	RuntimeError	Build a new set with a comprehension
b = a expecting a copy	Both names share one set	b = a.copy()
Using < expecting subset-or-equal	< means proper subset	<=

Best Practices Checklist

1. Use set(), never {}, for an empty set.
2. Use sets for uniqueness, fast membership tests, and group comparisons.
3. Use .discard() unless a missing element should be an error.
4. Use methods (not operators) when an argument might be a list, tuple, or range.
5. Never depend on the order of a set. Sort it when you need a predictable order.
6. Convert a large list to a set before running many in checks against it.
7. Use frozenset when you need a set that is hashable or must not change.
8. Prefer a set comprehension over mutating a set inside a loop.