Canonical Keys: Grouping Things That Match
A word-puzzle app has a big list of words and wants to show them in families: every family holds words that are rearrangements of one another, like "stop", "pots" and "tops". Comparing every word with every other word would be slow and messy. Instead, give each word a label that all its relatives share, and let a dictionary do the sorting into families.
The rule
Give every item a fingerprint; equal fingerprints share a bucket.
The fingerprint is called a canonical key: one standard form that every member of a group turns into, and no outsider does. For rearranged words, sorting the letters works, because "stop", "pots" and "tops" all sort to "opst".
from collections import defaultdict
def families(words):
groups = defaultdict(list) # key -> words with that key
for word in words:
key = "".join(sorted(word))
groups[key].append(word)
return list(groups.values())
families(["pots", "stop", "note", "cab", "tops", "tone"])
# [['pots', 'stop', 'tops'], ['note', 'tone'], ['cab']]The whole skill is choosing the key. It must pass two tests: every member produces the same key, and no non-member produces it. Some keys that pass:
- Rearranged words: the sorted letters, or a tuple of 26 letter counts.
- Emails that differ only in capital letters:
email.lower(). - Phone numbers typed in different styles: only the digits,
"".join(ch for ch in phone if ch.isdigit()).
A key must also be hashable to live in a dictionary. Strings, numbers and tuples are fine; a list is not, so turn counts into a tuple before using them as a key.
The shortcut
Ask: "What stays the same across every member of a group?" Whatever stays the same, written in one fixed form, is the key. Then the loop never changes: compute the key, append to its bucket.
pots and stop
Both sort to
opst. The first creates the bucket, the second joins it.
The trap is a key that is too loose. Word length is the same for every member of a family, but "note" and "pots" also share a length without being rearrangements. A good key is shared by members only.
Drills
Answer fast — trust the rule.
What canonical key does "".join(sorted("stop")) give?
Why would groups[list(counts)] fail where groups[tuple(counts)] works?
You want to group sign-ups whose emails differ only in capital letters. Which key?
Is len(word) a good key for grouping rearranged words?
Remember
- Give every item a fingerprint; equal fingerprints share a bucket.
- Shortcut: ask what stays the same across a group, and write it in one fixed form.
- Trap: a key that outsiders also produce, or a list, which cannot be a key.