Finding and grouping anagrams by Python

Question

input: ['abc', 'cab', 'cafe', 'face', 'goo']
output: [['abc', 'cab'], ['cafe', 'face'], ['goo']]

The problem is simple: it groups by anagrams. The order doesn't matter.

Of course, I can do this by C++ (that's my mother tongue). But, I'm wondering this can be done in a single line by Python. EDITED: If it's not possible, maybe 2 or 3 lines. I'm a newbie in Python.

To check whether two strings are anagram, I used sorting.

>>> input = ['abc', 'cab', 'cafe', 'face', 'goo']
>>> input2 = [''.join(sorted(x)) for x in input]
>>> input2
['abc', 'abc', 'acef', 'acef', 'goo']

I think it may be doable by combining map or so. But, I need to use a dict as a hash table. I don't know yet whether this is doable in a single line. Any hints would be appreicated!

Answer 1

A readable one-line solution:

output = [list(group) for key,group in groupby(sorted(words,key=sorted),sorted)]

For example:

>>> words = ['abc', 'cab', 'cafe', 'goo', 'face']
>>> from itertools import groupby
>>> [list(group) for key,group in groupby(sorted(words,key=sorted),sorted)]
[['abc', 'cab'], ['cafe', 'face'], ['goo']]

The key thing here is to use itertools.groupby from the itertools module which will group items in a list together.

The list we supply to groupby has to be sorted in advanced so we pass it sorted(words,key=sorted). The trick here is that sorted can take a key function and will sort based on the output from this function, so we pass sorted again as the key function and this will will sort the words using the letters of the string in order. There's no need to define our own function or create a lambda.

groupby takes a key function which it uses to tell if items should be grouped together and again we can just pass it the built-in sorted function.

The final thing to note is that the output is pairs of key and group objects, so we just take the grouper objects and use the list function to convert each of them to a list.

(BTW - I wouldn't call your variable input as then your hiding the built-in input function, although it's probably not one you should be using.)

Answer 2

the unreadable, one-line solution:

>>> import itertools
>>> input = ['abc', 'face', 'goo', 'cab', 'cafe']
>>> [list(group) for key,group in itertools.groupby(sorted(input, key=sorted), sorted)]
[['abc', 'cab'], ['cafe', 'face'], ['goo']]

(well, it is really 2 lines if you count the import...)