使用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作为哈希表。我还不知道是否能够在一行内完成。欢迎提供任何提示！

- Nullptr

---

为什么你想在一行中做这件事？ - Adrien Plisson

这只是一种脑筋急转弯。 - Nullptr

我已经编辑过了，我只想尽量减少代码行数。 - Nullptr

在 Ruby 中：xs.group_by { |x| x.chars.sort.join }.values。我想知道为什么 Python 没有（或者有吗？）一个 group_by 函数在标准库中（itertools.groupby() 只能对连续的元素进行分组）。有人知道吗？ - tokland

此外，请查看讨论部分：https://leetcode.com/problems/group-anagrams/，那里的人们提供了许多有趣的解决方案。 - funnydman

你实际上想要分组列表吗——即仅查找连续的同字母异序词元素？还是要根据它们的排序形式将元素分类？换句话说——如果输入为['abc'，'def'，'cab']，那么'abc'和'cab'是否应该被分组在一起？ - Karl Knechtel

Answer 1

一种可读的单行解决方案：

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模块中的groupby函数，它可以将列表中的项分组。

我们需要提前对传递给groupby的列表进行排序，因此我们将其传递给sorted(words,key=sorted)。这里的诀窍是sorted可以接受一个键函数，并根据该函数的输出进行排序，因此我们再次将sorted作为键函数传递，这将按顺序使用字符串的字母对单词进行排序。不需要定义自己的函数或创建lambda。 groupby接受一个键函数，用于确定哪些项应该分组，我们可以再次将内置的sorted函数传递给它。

最后需要注意的是输出是键和组对象的成对出现，因此我们只需取出组对象并使用list函数将它们转换为列表。

（顺便说一下 - 我不会将您的变量命名为input，因为这会隐藏内置的input函数，尽管这可能不是您应该使用的函数。）

- David Webb

---

@wutz - 你是对的，它需要在初始排序中处理长度。会去做。 - David Webb

@wutz - 现在已经修复了，只需将 sorted(words) 更改为 sorted(words,key=sorted) 即可。 - David Webb

@wutz - 谢谢，感谢你在测试中的帮助。 :-) - David Webb

感谢您的精彩解释。我正在努力理解groupby（）中的“键”和“键函数”的工作方式。我发现在您的示例中，如果不为groupby（）指定keyfunc，则结果中的键将是'abc'，'cab'...与列表元素相同。然而，在使用sorted作为keyfunc之后，键将变为['a'，'b'，'c']......从每个组对象中基本上拼出来的。您能否解释一下为什么会这样做呢？谢谢。 - Bowen Liu

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

(好吧，如果你算上导入的话，其实是两行...)

（嗯，如果您计算导入语句，实际上这是两行...）

- Adrien Plisson

---

如果变位词在输入中不相邻，则此方法会失败。 - wutz

Answer 3

不是一行代码的解决方案，而是一个完整的解决方案...

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

- yurib

Answer 4

可读性更强的版本：

from itertools import groupby
from operator import itemgetter

def norm(w):
  return "".join(sorted(w))

words = ['abc', 'cba', 'gaff', 'ffag', 'aaaa']

words_aug = sorted((norm(word), word) for word in words)

grouped = groupby(words_aug, itemgetter(0))

for _, group in grouped:
  print map(itemgetter(1), group)

一句话概括：

print list(list(anagrams for _, anagrams in group) for _, group in groupby(sorted(("".join(sorted(word)), word) for word in words), itemgetter(0)))

输出：

[['aaaa'], ['abc', 'cba'], ['ffag', 'gaff']]

- wutz

---

+1，为了提高可读性，我更喜欢使用“[[anagrams...”而不是“list(list(anagrams” - neurino

Answer 5

Dave的回答很简洁，但是groupby所需的排序是一个O(n log(n))操作。更快的解决方案是:

from collections import defaultdict

def group_anagrams(strings):
    m = defaultdict(list)

    for s in strings:
        m[tuple(sorted(s))].append(s)

    return list(m.values())

- kakarukeys

---

“groupby”方法使用“collections.Counter”作为键，而不是“sorted”。在这种情况下，它是线性的。但是，“sorted”实际上非常快，我怀疑除非单词非常长，否则使用“sorted”更快。 - Stef

@Stef，时间复杂度是针对传入group_anagrams的字符串列表长度而不是传入键函数的字符串长度。将键函数更改为Counter并不能帮助Dave的答案，因为在groupby调用之前仍然需要进行sorted操作，所以时间复杂度仍然是O(n log(n))。但你说对了一件事，如果n不是很大（几百万），实际运行时间可能差不多。 - kakarukeys

哦，你说得对。我有点混淆了。Dave的答案在字符串列表上使用了sorted，并且将其作为每个字符串调用的关键字。当我读到你的答案中的“排序”时，第一反应想到的是关键字。 - Stef

Answer 6

from itertools import groupby

words = ['oog', 'abc', 'cab', 'cafe', 'face', 'goo', 'foo']

print [list(g) for k, g in groupby(sorted(words, key=sorted), sorted)]

结果：

[['abc', 'cab'], ['cafe', 'face'], ['foo'], ['oog', 'goo']]

你不能仅仅使用groupby函数，因为它只能将连续的元素按照你的键函数产生相同结果的方式进行分组。

简单的解决方案是先使用与分组相同的函数对单词进行排序。

- Acorn

---

是的，我忽略了这一点，还有就是这些单词必须是相邻的。已经修复了。 - Acorn

Answer 7

虽然评论中的方法是100%正确的，如果你想不使用导入和内置函数来解决问题（我不知道这是否为一个脑筋急转弯），那么这里有一个方法。

def sort_anagrams(li):
        new_li = []
    for i in li:
        tree = False
        for j in new_li:
            if sorted(i) == sorted(j[0]):
                j.append(i)
                tree = True
        if not tree:
            new_li.append([i])
    return new_li

在使用中：

list_of = ['abc', 'face', 'goo', 'cab', 'cafe']
print(sort_anagrams(list_of))

输出：

[['abc', 'cab'], ['cafe', 'face'], ['goo']]

- Harel co