Group Word Clusters

Problem Statement

You're given a list of lowercase words. Two words belong together if one can be rearranged into the other — that is, they're made of exactly the same letters, the same number of times each, just possibly in a different order. Group the words this way, and print each group on its own line.

To make the output exact and predictable, follow two ordering rules: within a group, print its words sorted alphabetically; and print the groups themselves ordered by their shared "signature" — the letters of any word in the group, sorted alphabetically — from earliest to latest alphabetically.

Input Format

The input has exactly two lines:

• Line 1: a single integer n, the number of words.
• Line 2: the n words, separated by single spaces, each made only of lowercase letters.

Output Format

Print one line per group of words that share the same letters. Each line contains that group's words, sorted alphabetically and separated by single spaces. Print the groups themselves in ascending order of their signature (the sorted letters shared by the group).

Example Walkthrough

Take the first sample: eat tea tan ate nat bat. Computing each word's signature (its letters sorted alphabetically): eat -> aet, tea -> aet, tan -> ant, ate -> aet, nat -> ant, bat -> abt. Grouping by signature gives three groups: signature aet contains eat, tea, ate; signature ant contains tan, nat; signature abt contains just bat. Sorting the words alphabetically inside each group: aet becomes ate eat tea; ant becomes nat tan; abt stays bat. Finally, ordering the three groups by their signature string — comparing abt, aet, and ant character by character, the second letter (b, e, n) decides the order — gives abt first, then aet, then ant. That produces the three output lines: bat, then ate eat tea, then nat tan.

Approach

The key realization is that "made of the same letters, possibly reordered" has a simple, checkable test: two words are anagrams of each other exactly when sorting each word's letters produces the same string. That sorted string is a signature that's identical for every word in a group and different across groups.

With that, the grouping itself is a single pass: build a dictionary that maps each signature to the list of words seen so far with that signature, and for every word in the input, compute its signature and append it to the matching list (creating a new list if the signature hasn't been seen yet). After this pass, every group is fully formed.

The last step is producing output that's exactly reproducible no matter how the groups happened to be built internally. Anagram grouping alone doesn't specify an order for the words within a group or for the groups themselves, so this problem pins both down explicitly: sort each group's words alphabetically, and sort the groups by their signature. Since the signature is just a string, "sort by signature" is an ordinary alphabetical sort of those signature strings — no special comparison logic is needed beyond Python's default string ordering.

Common Mistakes

• Ordering the groups by something other than their signature — for example, by the order their first word happened to appear in the input, or by the alphabetically smallest word in the group. Either of these can produce a different group order than sorting by signature does, since a group's smallest word and its signature don't always agree on which group should come first (a group like ate eat tea has signature aet, which can sort differently than its own smallest word ate relative to another group's signature). The output only matches exactly when groups are ordered by signature specifically.
• Forgetting to sort the words within each group. Even if the grouping itself is correct, printing a group's words in whatever order they were encountered in the input (rather than alphabetically) produces output that looks right at a glance but won't match character-for-character.
• Computing the signature with something other than a full sort of the letters — for instance, sorting only the unique letters, or counting letters without preserving how many of each appear. A signature built from unique letters only would incorrectly treat "aab" and "ab" as anagrams, even though "aab" has two a's and "ab" has only one.