Sets — a collection without duplicates

The problem we are solving

A day's sales arrive as a list, one entry per sale:

sold = ["pen", "bag", "pen", "ink", "pen"]

The question: how many different products sold? len(sold) says five, but that is the number of sales. There were three distinct products.

The previous chapters can manage it — start an empty list, and for each item check if item not in unique: before adding. Six lines, and it works.

But if the question is "which products sold on both Monday and Tuesday?" you need two nested loops. "Monday only?" — another. These questions are common enough to have their own branch of mathematics, and in Python that mathematics can be written directly.

A set is the container for it: it holds no duplicates, and answers "in both", "in one but not the other" with a single character.

By the end of this chapter you can

• Build a set, and strip duplicates out of a list
• Compare two sets with |, &, - and ^
• Explain why {} is not an empty set
• Know that a set has no order, and when that matters
• Write the pattern that removes duplicates while keeping order

Prerequisites: Dictionaries — pairs of key and value.

A set — a collection without duplicates

sold = ["pen", "bag", "pen", "ink", "pen"]

unique = set(sold)
print(sorted(unique))
print(len(unique))

['bag', 'ink', 'pen']
3

set(...) takes a list and drops the duplicates. Three pens become one.

Notice sorted() around the printing, which is deliberate — the reason arrives shortly.

You can also write one directly, with curly brackets:

letters = {"a", "b", "a"}
print(sorted(letters))
print(len(letters))

['a', 'b']
2

The second "a" quietly vanished. No error — a set has no concept of the same thing appearing twice.

{} is not an empty set

not_a_set = {}
real_set = set()

print(type(not_a_set))
print(type(real_set))

<class 'dict'>
<class 'set'>

Curly brackets meant dictionaries first, so an empty {} stayed a dictionary. For an empty set you have to write set().

The mistake is silent: start with {}, call .add(), and you get an AttributeError that makes it look as though add is the problem.

There is no order

This is a set's most important limitation, and its most misunderstood property.

The things in a set are in no order. There are no indexes and no slices:

tags = {"new", "sale"}
print(tags[0])

TypeError: 'set' object is not subscriptable

And the order you see when printing one is not dependable — run the same program twice and it can differ. That is why every example in this chapter sorts before printing: what you see from printing a set directly is not guaranteed to be what you see next time.

The shortest way to strip duplicates from a list is list(set(sold)), and it throws the original order away. When order matters, use a set and a list together:

sold = ["pen", "bag", "pen", "ink", "bag"]
seen = set()
unique = []

for item in sold:
    if item not in seen:
        seen.add(item)
        unique.append(item)

print(unique)

['pen', 'bag', 'ink']

The list keeps the order and the set remembers what has been seen. That pairing is a very common pattern.

Adding and removing

tags = {"new"}

tags.add("sale")
tags.add("new")
print(sorted(tags))

tags.discard("gone")
tags.remove("sale")
print(sorted(tags))

['new', 'sale']
['new']

add puts one thing in — and if it is already there, nothing happens and nothing complains. A list's append would have made a second copy; a set does not.

Removing comes in two forms, and the difference is useful:

tags = {"new"}
tags.remove("gone")

KeyError: 'gone'

remove stops when it does not find the thing; discard shrugs. If the thing is supposed to be there, write remove so that its absence is caught.

Comparing two sets

This is where sets genuinely earn their place:

monday = {"rafi", "ahmed", "bilal"}
tuesday = {"ahmed", "dia"}

print(sorted(monday | tuesday))
print(sorted(monday & tuesday))
print(sorted(monday - tuesday))
print(sorted(monday ^ tuesday))

['ahmed', 'bilal', 'dia', 'rafi']
['ahmed']
['bilal', 'rafi']
['bilal', 'dia', 'rafi']

Four symbols, four questions:

• | — in either (union). Everyone who came across the two days.
• & — in both (intersection). Who came on both days.
• - — in the first and not the second (difference). Who came on Monday only.
• ^ — in exactly one (symmetric difference). Who came on one day but not both.

Notice - cares about order: monday - tuesday and tuesday - monday give different answers. The other three read the same both ways.

Writing those four with loops would take several lines each, with a good chance of getting at least one wrong.

What can go in

The same rule as dictionary keys: whatever you put in has to be immutable.

s = set()
s.add([1, 2])

TypeError: unhashable type: 'list'

Word for word the same message, for the same reason — a set uses hashing underneath too. Text, numbers and tuples are fine; lists and dictionaries are not.

A complete example

sales.py:

# Which products sold on both days, and which only on one
monday = ["pen", "bag", "pen", "ink"]
tuesday = ["ink", "bottle", "pen", "ink"]

mon = set(monday)
tue = set(tuesday)

print("Monday sold    :", sorted(mon), f"({len(monday)} sales, {len(mon)} products)")
print("Tuesday sold   :", sorted(tue), f"({len(tuesday)} sales, {len(tue)} products)")
print()
print("Either day     :", sorted(mon | tue))
print("Both days      :", sorted(mon & tue))
print("Monday only    :", sorted(mon - tue))
print("Exactly one day:", sorted(mon ^ tue))
print()
print("Was ink sold on Monday?", "ink" in mon)

Monday sold    : ['bag', 'ink', 'pen'] (4 sales, 3 products)
Tuesday sold   : ['bottle', 'ink', 'pen'] (4 sales, 3 products)

Either day     : ['bag', 'bottle', 'ink', 'pen']
Both days      : ['ink', 'pen']
Monday only    : ['bag']
Exactly one day: ['bag', 'bottle']

Was ink sold on Monday? True

Three things worth noticing.

The original lists were kept. len(monday) reports four sales, len(mon) three products. Once converted to a set the number of sales is gone — so the set is not a replacement for the data, it is a tool for asking one kind of question about it.

sorted() before every print. Without it the order would look arbitrary, and could change between runs.

It says "ink" in mon, not "ink" in monday. Both give True, but searching a set is faster than searching a list — in a list Python compares one item at a time, in a set it hashes straight to the place. With four things that is meaningless; with forty thousand it is not.

When it breaks

AttributeError: 'dict' object has no attribute 'add' Something wrote s = {} meaning a set, but that is an empty dictionary. Write s = set().

TypeError: 'set' object is not subscriptable Something wrote s[0]. A set has no order, so it has no indexes. If you need a particular item you probably wanted a list or a dictionary; otherwise sorted(s) gives you a list.

KeyError: 'gone' remove was asked to drop something the set does not contain. If either state is normal, use discard.

TypeError: unhashable type: 'list' An attempt to put a list into a set. Convert it with tuple(...).

The order came out scrambled after list(set(...)) That is expected; sets have no order. If you need it, use the seen pattern above, or sorted().

I compared two sets with == and got True despite a different order Correctly so. Two sets are equal when they contain the same things — order plays no part. [1, 2] == [2, 1] is False for lists; {1, 2} == {2, 1} is True for sets.

Your turn

Write a file called visitors.py with three lists of visitors, one per day, where some names appear on more than one day.

Then print:

1. How many visits each day, and how many distinct people
2. How many distinct people across all three days
3. The people who came on all three days
4. The people who came on the first day only
5. The people who came on exactly one of the first two days

Then two experiments:

• Strip duplicates two ways — list(set(...)) and the seen pattern above — and print both results side by side. What is the difference?
• Try to make an empty set with {} and call .add() on it. Which error comes back, and which kind of object does the message name?

The second is small, and seeing it once with your own eyes means that mistake will never cost you ten minutes again.