通过Python查找和分组字谜 [英] Finding and grouping anagrams by Python

问题描述

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

问题很简单:按 anagrams 分组.顺序无关紧要.

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

当然，我可以使用C ++来做到这一点(这是我的母语).但是，我想知道能否通过 Python 在一行中完成. 如果不可能的话，大概2或3行.我是Python的新手.

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']

我认为将map组合在一起可能是可行的.但是，我需要使用dict作为哈希表.我尚不知道这是否可以单行执行.任何提示将不胜感激！

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!

推荐答案

可读的单行解决方案:

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

例如:

>>> 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']]

这里的关键是使用itertools模块中的 itertools.groupby 会将列表中的项目分组在一起.

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

我们提供给groupby的列表必须进行高级排序，因此我们将其传递给sorted(words,key=sorted).这里的窍门是sorted可以采用键函数，并将基于该函数的输出进行排序，因此我们再次传递sorted作为键函数，这将使用字符串的字母对单词进行排序.无需定义我们自己的函数或创建lambda.

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带有一个关键函数，用于告知是否应将项目分组在一起，而我们可以再次将其内置的sorted函数传递给它.

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.

最后要注意的是，输出是成对的键和组对象，因此我们只需要使用grouper对象，并使用list函数将它们中的每一个转换为列表.

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.

(顺便说一句，我不会将您的变量input称为隐藏内置的input函数，尽管您可能不应该使用它.)

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

这篇关于通过Python查找和分组字谜的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！