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

问题很简单：它按anagrams分组。顺序无关紧要。

当然，我可以用 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左右可能是可行的。但是，我需要使用 adict作为哈希表。我还不知道这在一行中是否可行。任何提示将不胜感激！

4

7 回答 7

9

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

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模块itertools，它将列表中的项目组合在一起。

我们提供给的列表groupby必须预先排序，所以我们通过它sorted(words,key=sorted)。这里的技巧是它sorted可以接受一个键函数并根据该函数的输出进行排序，因此我们sorted再次作为键函数传递，这将使用字符串的字母按顺序对单词进行排序。无需定义我们自己的函数或创建lambda.

groupby接受一个关键函数，它用来告诉项目是否应该组合在一起，我们可以再次将其传递给内置sorted函数。

最后要注意的是，输出是一对 key 和 group 对象，所以我们只取 grouper 对象并使用list函数将它们中的每一个转换为一个列表。

（顺便说一句 - 我不会调用你的变量input，因为你隐藏了内置input函数，尽管它可能不是你应该使用的。）

于 2011-11-18T11:38:03.497 回答
3

不可读的单行解决方案：

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

（好吧，如果算上进口，那真的是两行......）

于 2011-11-18T11:34:58.150 回答
2

不是一个班轮，而是一个解决方案......

d = {}
for item in input:
  s = "".join(sorted(item))
  if not d.has_key(s):
    d[s] = []
  d[s].append(item)
input2 = d.values()
于 2011-11-18T11:29:12.980 回答
2

可读版本：

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']]
于 2011-11-18T11:31:23.167 回答
2

戴夫的回答很简洁，但是所需的排序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())
于 2017-06-03T14:43:46.930 回答
1 
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 函数，因为它只会将您的关键函数产生相同结果的顺序元素组合在一起。

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

于 2011-11-18T11:41:56.023 回答
0

尽管如果您在不使用导入及其内置函数（idk 用于脑筋急转弯）的情况下尝试解决，那么评论是 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']]
于 2021-10-01T17:04:49.723 回答