分组anagram词的算法

给定一组单词,我们需要找到anagram单词并使用最佳算法单独显示每个类别.

输入:

man car kile arc none like

输出:

man
car arc
kile like
none

我现在开发的最佳解决方案是基于散列表,但我正在考虑将anagram字转换为整数值的等式.

示例:man =>'m'+'a'+'n'但这不会给出唯一值.

有什么建议吗？

---

请参阅C#中的以下代码:

string line = Console.ReadLine();
string []words=line.Split(' ');
int[] numbers = GetUniqueInts(words);
for (int i = 0; i < words.Length; i++)
{
    if (table.ContainsKey(numbers[i]))
    {
        table[numbers[i]] = table[numbers[i]].Append(words[i]);
    }
    else
    {
        table.Add(numbers[i],new StringBuilder(words[i]));
    }

}

问题是如何开发GetUniqueInts(string [])方法.

1> Jon Skeet..：

---

根本不需要使用自定义哈希函数.在您的平台上使用普通的字符串哈希函数.重要的是使哈希表的关键字成为"排序单词"的概念 - 其中单词按字母排序,因此"car"=>"acr".所有字谜都将具有相同的"排序字".

只需要从"排序单词"到"排序单词的单词列表"的哈希值.在LINQ中,这非常容易:

using System;
using System.Collections.Generic;
using System.Linq;

class FindAnagrams
{
    static void Main(string[] args)
    {
        var lookup = args.ToLookup(word => SortLetters(word));

        foreach (var entry in lookup)
        {
            foreach (var word in entry)
            {
                Console.Write(word);
                Console.Write(" ");
            }
            Console.WriteLine();
        }
    }

    static string SortLetters(string original)
    {
        char[] letters = original.ToCharArray();
        Array.Sort(letters);
        return new string(letters);
    }
}

样品用途:

c:\Users\Jon\Test>FindAnagrams.exe man car kile arc none like
man
car arc
kile like
none

---

实际上,如果将其限制为26个字符,则可以非常容易地在O(n)中完成排序.我的路线的主要优点是简单,说实话 - 它显然是正确的,而不用担心太多的数学问题.我喜欢简单的解决方案

2> 小智..：

---

我使用了Godel启发的方案:

将素数P_1到P_26分配给字母(以任何顺序,但是为了获得小的哈希值,最好给出普通字母小素数).

建立了单词中字母的直方图.

然后,哈希值是每个字母的相关素数的乘积,其增加到其频率的幂.这为每个字谜提供了独特的价值.

Python代码:

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


def get_frequency_map(word):
    map = {}

    for letter in word:
        map[letter] = map.get(letter, 0) + 1

    return map


def hash(word):
    map = get_frequency_map(word)
    product = 1
    for letter in map.iterkeys():
        product = product * primes[ord(letter)-97] ** map.get(letter, 0)
    return product

这巧妙地将寻找subanagrams的棘手问题转化为(也称为棘手的)分解大数字的问题......

---

但任意大的单词将需要任意大的整数.您也可以使用排序后的单词(或频率映射)作为散列键.

3> James Brady..：

---

giggles的Python版本:

from collections import defaultdict
res = defaultdict(list)
L = "car, acr, bat, tab, get, cat".split(", ")

for w in L:
    res["".join(sorted(w))].append(w)

print(res.values())