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: pans lamp pear naps palm snap. Computing each word's signature (its letters sorted alphabetically): pans -> anps, lamp -> almp, pear -> aepr, naps -> anps, palm -> almp, snap -> anps. Grouping by signature gives three groups: signature anps contains pans, naps, snap; signature almp contains lamp, palm; signature aepr contains just pear. Sorting the words alphabetically inside each group: anps becomes naps pans snap; almp becomes lamp palm; aepr stays pear. Finally, ordering the three groups by their signature string — comparing aepr, almp, and anps character by character, all three start with a, so the second letter (e, l, n) decides the order — gives aepr first, then almp, then anps. That produces the three output lines: pear, then lamp palm, then naps pans snap.

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. The first sample shows this: ordering by smallest word would print lamp palm before pear, because lamp comes before pear alphabetically, but their signatures almp and aepr sort the other way round, so pear must come first. 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.