2

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

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

我想列出这样的字谜列表 -

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

我试图做这样的事情：

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

但它不起作用。输出是：

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

另外，我不想使用任何导入（字符串除外）。错误是什么？

4

4 回答 4

3

请注意，您的原始方法实际上是 O(#words 2 ) 时间，因此不适用于可能超过 10000 个单词的大型数据集。

groupby 单线：

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

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

defaultdict 三线：

使用collections.defaultdict，您可以执行以下操作：

anagrams = defaultdict(list)
for w in words:
    anagrams[tuple(sorted(w))].append(w)

至于如果在没有任何导入的情况下按照您的原始方式进行操作，您可以模拟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 的回答中。）

地图减少：

这个问题也是 map-reduce 的典型问题，您使用的归约键是排序后的字母（或者更有效的是哈希）。这将允许您大规模并行化问题。

如果我们假设单词的长度是有界的，则groupby解是O(#words log(#words))，而哈希解是预期的O(#words)。在不太可能的情况下，单词的长度是任意的，排序（O(length log(length))每个单词）比使用与顺序无关的字母散列（每个单词）效率低O(length)。可悲的是， collections.Counter 不可散列，因此您必须自己编写。

于 2012-06-02T08:20:10.423 回答
2 
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)

于 2012-06-02T08:27:06.300 回答
0

您可以通过谷歌搜索一次找到单个单词的字谜的各种解决方案。很可能会有比明显的“搜索我知道的所有单词并查看它们是否具有相同字母”更有效的求解器。

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

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

一旦你有了它，将它概括为一个单词列表是微不足道的：

[anagrams(word) for word in words]
于 2012-06-02T08:12:06.607 回答
0

这个应该以您喜欢的风格来解决问题

[[w, w1] for w1 in words for w in words if w!=w1 and sorted(w1)==sorted(w)][::2]
于 2012-06-02T08:38:58.353 回答