python中anagram列表

Question

如果我的输入是这样的列表：

words = ['cat','act','wer','erw']

我想列一个这样的字谜列表-

^{pr2}$

我试过这样做：

[[w1 for w in words if w!=w1 and sorted(w1)==sorted(w)] for w1 in words]

但它不起作用。结果是：

[['cat'], ['act'], ['wer'], ['erw']]

另外，我不想使用任何导入（字符串除外）。怎么了？在

Answer 1

你可以通过google一次找到一个单词的变音图的各种解决方案。很可能会有一个更有效的解决方案，而不是显而易见的“搜索所有我知道的单词，看看它们是否有相同的字母”。在

一旦你有了一个，你就可以把它放到一个函数中：

def anagrams(word):
    "return a list of all known anagrams of *word*"

一旦你有了这些，把它概括成一系列单词就不重要了：

^{pr2}$

Answer 2

请注意，您的原始方法实际上是O（#words²）时间，因此无法处理超过10000个单词的大型数据集。在

---

按一行代码分组：

我见过的itertools.groupby中最优雅的最奇怪的用例之一：

>>> [list(v) for k,v in groupby(sorted(words,key=sorted),sorted)]
[['cat', 'act'], ['wer', 'erw']]

---

defaultdict三行代码：

使用collections.defaultdict，您可以：

^{pr2}$

至于如果不使用任何导入的原始方式执行，则可以模拟collections.defaultdict，如下所示：

anagrams = {}
for w in words:
    key = tuple(sorted(w))
    anagrams.setdefault(key,[]).append(w)

示例：

>>> anagrams
{('e', 'r', 'w'): ['wer', 'erw'], ('a', 'c', 't'): ['cat', 'act']}

（也写在whi's answer中。）

---

地图减少：

这个问题也是map reduce的海报子问题，其中您使用的reduction键是排序后的字母（或者更有效地说是散列）。这将允许您大规模地并行处理问题。在

---

如果我们假设单词的长度是有界的，那么groupby解是O(#words log(#words))，而哈希解是{}。在不太可能的情况下，单词的长度是任意的，排序（O(length log(length))每个单词）比使用字母顺序无关的散列（每个单词O(length)）效率低。悲哀地，集合。计数器不可散列，因此您必须自己编写。在

Answer 3

words = ['cat','act','wer','erw']
dic={}
for w in words:
    k=''.join(sorted(w))
    dic.setdefault(k,[])
    dic[k].append(w)
print dic.values()

这在性能上更好：O（n）