Programming Tutorials

Sets

Beginner30 min

Use sets for fast membership tests, removing duplicates and set algebra with union, intersection and difference.

Builds on
What you will learn
  • Create sets and add, discard and test items
  • Remove duplicates from a list
  • Combine sets with |, &, - and ^
  • Use frozenset when a set must be hashable
On this page

Sometimes you do not care about order or position, only about whether something is there. Is this user already registered? Which words appear in both documents? A set is an unordered collection of unique items built for exactly those questions. It rests on the same hashing idea as dictionary keys, which the fundamentals lesson on maps and sets explains.

Creating a set

Curly braces with bare items make a set, and duplicates are dropped.

set_create.py
colors = {"red", "green", "blue", "red"}
print(sorted(colors), len(colors))
Output
['blue', 'green', 'red'] 3

A set has no positions, so s[0] is an error and the printing order is not something to rely on. The example wraps the set in sorted(...) so the output is the same on every run.

The empty case is the trap: {} is an empty dict, so spell an empty set set().

set_empty.py
empty_set = set()
empty_dict = {}
print(type(empty_set).__name__, type(empty_dict).__name__)
Output
set dict

Changing a set

add inserts an item. discard removes it if present and does nothing otherwise, whereas remove raises KeyError for a missing item. x in s is very fast, and the last lesson of this module shows by how much.

set_change.py
colors = {"red", "green", "blue"}
colors.add("yellow")
colors.discard("purple")
colors.discard("red")
print(sorted(colors))
print("blue" in colors)
Output
['blue', 'green', 'yellow']
True
colors = {"blue"}
colors.remove("purple")
Output
KeyError: 'purple'

Removing duplicates

set(my_list) is the quickest way to drop duplicates, though the original order is lost. The exercise below shows how to keep it.

set_dedupe.py
numbers = [3, 1, 3, 2, 1]
print(sorted(set(numbers)))
Output
[1, 2, 3]

Items must be hashable, so you can store numbers, strings and tuples but not lists:

print({[1, 2]})
Output
TypeError: cannot use 'list' as a set element (unhashable type: 'list')
set_tuples.py
print({(1, 2), (1, 2)})
Output
{(1, 2)}

Set algebra

The four operators match the diagrams from school maths:

Operator Meaning
a | b union: in either set
a & b intersection: in both
a - b difference: in a but not b
a ^ b symmetric difference: in exactly one
set_algebra.py
python_fans = {"Ada", "Grace", "Linus", "Guido"}
rust_fans = {"Linus", "Ferris", "Grace"}


print(sorted(python_fans | rust_fans))
print(sorted(python_fans & rust_fans))
print(sorted(python_fans - rust_fans))
print(sorted(python_fans ^ rust_fans))
Output
['Ada', 'Ferris', 'Grace', 'Guido', 'Linus']
['Grace', 'Linus']
['Ada', 'Guido']
['Ada', 'Ferris', 'Guido']

a <= b asks whether a is a subset of b, and a.isdisjoint(b) asks whether they share nothing. Each operator has a method twin (union, intersection, difference, symmetric_difference). The methods accept any iterable, so a list works, but the operators need two sets.

set_tests.py
python_fans = {"Ada", "Grace", "Linus", "Guido"}


print({"Ada"} <= python_fans)
print(python_fans.isdisjoint({"Zed"}))
print(sorted(python_fans.intersection(["Ada", "Zed"])))
Output
True
True
['Ada']

frozenset

A frozenset is an immutable set. It supports all the read-only operations but has no add or remove.

frozenset_basic.py
fs = frozenset({1, 2, 3})
print(fs, 2 in fs)
Output
frozenset({1, 2, 3}) True
fs = frozenset({1, 2, 3})
fs.add(4)
Output
AttributeError: 'frozenset' object has no attribute 'add'. Did you mean to use a 'set' object?

Because it cannot change, a frozenset is hashable, so it can be a dictionary key or an element of another set, and the order in which the names were written does not matter.

frozenset_key.py
rooms = {frozenset({"Ada", "Alan"}): "lab"}
print(rooms[frozenset({"Alan", "Ada"})])
Output
lab

(Python 3.15 adds the same idea for dicts as frozendict, covered in the previous lesson.)

Common pitfalls

  • {} is not an empty set. It is an empty dict. Use set().
  • Relying on set order. Sets are unordered. Sort them for display or tests.
  • Putting a list in a set. Lists are unhashable. Use a tuple, or a frozenset for nested sets.
  • Using remove when the item may be absent. It raises KeyError. Use discard.
  • Using | with a list. {1} | [2] is a TypeError. Call {1}.union([2]) or convert the list first.
  • Expecting set(text) to give words. It gives the set of characters. Use set(text.split()) for words.
ExerciseCount the distinct letters

Predict the two lines this prints, then run the file. Input: none. Expected output: a number and then a sorted list of letters.

predict_set.py
letters = set("mississippi")
print(len(letters))
print(sorted(letters))
Show solution
4
['i', 'm', 'p', 's']

A string is a sequence of characters, so set("mississippi") keeps one of each distinct letter. There are four, and sorted puts them in alphabetical order.

ExerciseCommon friends

Ada’s friends are ["Grace", "Alan", "Linus", "Margaret"] and Ben’s are ["Alan", "Margaret", "Dennis", "Alan"]. Print the sorted list of friends they share, the sorted list of friends only Ada has, and Ben’s list with duplicates removed but the original order kept.

Input: the two lists. Expected output:

['Alan', 'Margaret']
['Grace', 'Linus']
['Alan', 'Margaret', 'Dennis']
Show solution
common_friends.py
ada = ["Grace", "Alan", "Linus", "Margaret"]
ben = ["Alan", "Margaret", "Dennis", "Alan"]


print(sorted(set(ada) & set(ben)))
print(sorted(set(ada) - set(ben)))


seen = set()
unique_in_order = []
for name in ben:
    if name not in seen:
        seen.add(name)
        unique_in_order.append(name)
print(unique_in_order)
Output
['Alan', 'Margaret']
['Grace', 'Linus']
['Alan', 'Margaret', 'Dennis']

The seen set gives a fast “have I met this before?” test while the list keeps the order. A one-line alternative is list(dict.fromkeys(ben)), which works because dict keys are unique and remember insertion order.

ExerciseWords only in the first text

Given first = "The cat sat on the mat" and second = "the dog sat", print the sorted list of words that appear in the first text but not the second, ignoring case.

Input: the two texts. Expected output: ['cat', 'mat', 'on'].

Show solution
unique_words.py
first = "The cat sat on the mat"
second = "the dog sat"


only_first = set(first.lower().split()) - set(second.lower().split())
print(sorted(only_first))
Output
['cat', 'mat', 'on']

Lowercasing first makes The and the the same word, and the set difference does the rest.

Summary

  • A set holds unique, hashable items with very fast in tests, and it has no order. Create an empty one with set().
  • |, &, - and ^ give union, intersection, difference and symmetric difference.
  • frozenset is the immutable, hashable version, usable as a dict key.

Next: slicing in depth.