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!
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.)