用Python查找和分组变位词

Question

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

这个问题很简单：就是要把字母异位词分组。顺序不重要。

当然，我可以用C++来做这个（这是我的母语）。但是，我在想这能不能用Python在一行代码中完成。补充：如果不行，也许可以用2到3行。我还是Python的新手。

为了检查两个字符串是否是字母异位词，我用了排序的方法。

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

我觉得可以通过结合使用map之类的来实现。但是，我需要用dict作为哈希表。我还不确定这能不能在一行中完成。任何提示都会很感激！

Answer 1

这不是一句话就能解决的问题，而是一个完整的解决方案...

d = {}
for item in input:
  s = "".join(sorted(item))
  if not d.has_key(s):
    d[s] = []
  d[s].append(item)
input2 = d.values()

Answer 2

这是一个看起来很复杂的、一行代码的解决方案：

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

(不过，如果你算上导入的那一行，其实是两行...)

Answer 3

这是一个简单易懂的一行解决方案：

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，它可以把列表中的项目分组在一起。

我们传给 groupby 的列表必须提前排好序，所以我们用 sorted(words,key=sorted) 来处理。这里的窍门是 sorted 可以接受一个关键函数，然后根据这个函数的输出进行排序，所以我们把 sorted 作为关键函数传进去，这样就能按照字符串中字母的顺序来排序单词。我们不需要自己定义函数或者创建 lambda。

groupby 需要一个关键函数来判断哪些项目应该被分在一起，我们同样可以直接传入内置的 sorted 函数。

最后要注意的是，输出是成对的键和组对象，所以我们只需要获取这些组对象，然后用 list 函数把它们转换成列表。

(顺便说一下，不要把你的变量命名为 input，因为那样会遮盖掉 内置的 input 函数，虽然这个函数可能也不是你需要用的。)