更好的方法来做字谜组

Question

正在处理下面的字谜分组问题。我目前的解决方案是按单个字符对每个单词进行排序，然后将相同的排序值映射到字典中。

想知道是否有更好的算法时间复杂度更低的想法？我正在考虑不做排序的方法，比如散列，但是散列也需要单词的顺序字符。

Post问题和我的代码，写在Python2.7.

问题,

给出一个单词列表，例如 [rats, star, arts, cie, ice]，将相同的字谜分组到桶中并输出它们。 [鼠、星、艺] [cie, 冰]

源代码,

from collections import defaultdict
def group_anagram(anagrams):
    result = defaultdict(list)
    for a in anagrams:
        result[''.join(sorted(list(a)))].append(a)
    return result

if __name__ == "__main__":
    anagrams = ['rats', 'star', 'arts', 'cie', 'ice']
    print group_anagram(anagrams)

Answer 1

质因数分解是唯一的，乘法顺序无关紧要。

您可以分配 a = 2, b = 3, c = 5, d = 7 等

然后 dab = 7 * 2 * 3 = 42 = 3 * 2 * 7 = 不好，所以你的哈希值是 42。

另一种选择是 hash(frozenset(collections.Counter(word).items()))

的有效实施

编辑：最快的可能是使用 26 位。对于单词中的每个字符，翻转对应的位。您可能会遇到一些冲突，在这种情况下，您可以在查找时进行重复数据删除

Answer 2

您目前的方法可能是最好的。为了测试事物，我使用了您的方法，@bigballer 的出色答案中的方法和使用计数元组作为键的第三种方法。为了对这些方法进行压力测试，我在大量（264,097 个单词）单词列表 yawl 上使用了它们，运行对每个函数执行 100 次，并计算每个方法的平均时间：

from collections import defaultdict
import timeit

def group_anagram1(anagrams):
    result = defaultdict(list)
    for a in anagrams:
        result[''.join(sorted(a))].append(a)
    return result.values()

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]

def group_anagram2(anagrams):
    result = defaultdict(list)
    for a in anagrams:
        n = 1
        for c in a:
            n *= primes[ord(c) - ord('a')]
        result[n].append(a)
    return result.values()

def group_anagram3(anagrams):
    result = defaultdict(list)
    for a in anagrams:
        counts = [0]*26
        for c in a:
            counts[ord(c) - ord('a')] += 1
        result[tuple(counts)].append(a)
    return result.values()



with open("yawl.txt") as f:
    words = f.readlines()
    words =[w.strip() for w in words]

print timeit.timeit("group_anagram1(words)", setup="from __main__ import group_anagram1,words",number = 100)/100.0
print timeit.timeit("group_anagram2(words)", setup="from __main__ import group_anagram2,words",number = 100)/100.0
print timeit.timeit("group_anagram3(words)", setup="from __main__ import group_anagram3,words",number = 100)/100.0

输出（在我的机器 YMMV 上）：

0.486009083239
0.64333226691
0.797640375079

真的，考虑到 yawl 的大小，所有方法都非常快，每个方法都用不到一秒的时间来处理超过 25 万个单词。尽管如此，您的原始方法显然是赢家。此外，它不限于拉丁文 'a' 到 'z' 字母表。至于为什么它是最好的——密钥直接由 Python 内置函数（运行优化的 C 代码）构造，但其他方法使用解释的 Python 代码。很难击败内置插件。

On Edit：我使用这个素数列表重新实现了第二种方法，排序后更频繁的字母（英语）被分配给更小的素数：

primes = [5,71,37,29,2,53,59,19,11,83,79,31,43,13,7,67,97,23,17,3,41,73,47,89,61,101]

它节省了几分之一秒的时间，但还不足以使其比第一种方法更快。

进一步编辑:

我对第二种方法进行了以下调整，重新运行了上面的代码（正如@bigballer 所建议的那样）：

primes = [5,71,37,29,2,53,59,19,11,83,79,31,43,13,7,67,97,23,17,3,41,73,47,89,61,101]
primes = {c:p for c,p in zip('abcdefghijklmnopqrstuvwxyz',primes)}

def group_anagram2(anagrams):
    result = defaultdict(list)
    for a in anagrams:
        n = 1
        for c in a:
            n *= primes[c]
        result[n].append(a)
    return result.values()

在这个版本中，前两种方法几乎持平，在我有限的测试中，基于素数的方法稍快一些（快了大约 8%）。尽管如此，我仍然认为第一种方法更可取，因为它不依赖于固定的字母表。

更好的方法来做字谜组

better ways to do anagram group

python

algorithm

anagram

python-2.7