collections: group the words

The collections module ships batteries-included containers. Two favourites:

from collections import Counter, defaultdict

Counter("banana")        # Counter({'a': 3, 'n': 2, 'b': 1})

groups = defaultdict(list)   # missing keys auto-create an empty list
groups["x"].append(1)        # no KeyError, no setdefault dance
groups                       # {'x': [1]}

A defaultdict(list) is perfect for bucketing items: index into it with a key and .append, and the empty list appears for free the first time.

Your task

Write group_anagrams(words) that groups words which are anagrams of each other (same letters, any order). Return a list of groups, where:

• each group is the list of words sharing a letter signature, in the order they appeared in the input, and
• the groups themselves are sorted by their first word.

group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
# [["bat"], ["eat", "tea", "ate"], ["tan", "nat"]]

group_anagrams(["abc"])         # [["abc"]]

Hint: give each word a signature — its letters sorted and rejoined into a string — so that anagrams collapse onto the same key. Bucket the words by signature (a defaultdict(list) saves you the empty-list dance), then return the buckets sorted by their first word.