# Sets and Frozensets — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/h-set

> Use sets for membership, de-duplication and set algebra.

## Unordered collections of unique items

A **`set`** is a hash table of keys without values: **membership tests, insertion and removal are O(1) on average**, and duplicates are impossible. Sets are the right tool for **de-duplication** (`set(items)`), fast **membership** checks against a collection used repeatedly, and **set algebra**: union `|`, intersection `&`, difference `-` and symmetric difference `^`, plus `issubset` (`<=`) and `isdisjoint`. Elements must be hashable. Sets are **unordered**: iteration order is arbitrary and may change between runs for strings, so do not rely on it (to de-duplicate while keeping order, use `dict.fromkeys(items)`). **`frozenset`** is an immutable, hashable set, usable as a dictionary key or as an element of another set (for example, to represent an unordered pair or a combination of tags). Set comprehensions (`{x.lower() for x in words}`) build sets directly. The cost of building a set is O(n), so converting a list to a set pays off only when you will perform several lookups.

## Set algebra for permissions and recommendations

Unions, intersections, differences and frozensets.

```python
required = {"orders:read", "orders:write"}
asha_perms = {"orders:read", "orders:write", "reports:read"}
ravi_perms = {"orders:read"}

print(required <= asha_perms)               # True: subset check
print(required - ravi_perms)                # {'orders:write'}: what Ravi is missing

bought_by_asha = {"pen", "ink", "pad"}
bought_by_meera = {"pen", "stapler"}
print(bought_by_asha & bought_by_meera)     # {'pen'}
print(bought_by_meera - bought_by_asha)     # {'stapler'}: recommend to Asha
print(bought_by_asha ^ bought_by_meera)     # items bought by exactly one of them

emails = ["A@x.com", "b@x.com", "a@x.com", "c@x.com", "B@x.com"]
unique_ordered = list(dict.fromkeys(e.lower() for e in emails))
print(unique_ordered)                       # ['a@x.com', 'b@x.com', 'c@x.com']

# frozenset as a key: unordered pairs of products bought together
pair_counts = {}
for basket in [{"pen", "ink"}, {"ink", "pen", "pad"}, {"pad", "pen"}]:
    items = sorted(basket)
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            pair = frozenset((items[i], items[j]))
            pair_counts[pair] = pair_counts.get(pair, 0) + 1
print(pair_counts[frozenset({"pen", "ink"})])   # 2
```

## A guest list at the door

A set is the bouncer's guest list: checking whether a name is on it is instant, nobody can be on it twice, and two lists can be merged or compared in one step. It does not care in which order guests were added.

**Quiz:** What is the most efficient way to remove duplicates from a list while preserving the original order?

- [ ] set(items)
- [ ] sorted(items)
- [ ] items.sort()
- [x] list(dict.fromkeys(items))

*Answer:* list(dict.fromkeys(items)). dict.fromkeys keeps first occurrences in insertion order; a plain set does not preserve order.