从字典中获得字谜名单从字典中获得字谜名单(get list of anagrams from a d

基本上，字谜像string.Eg的排列stack ， sackt ， stakc所有都是字谜stack （上面的字认为是没有意义的）。反正你可能已经明白了我的意思基本。

现在，我想的列表anagrams给万个字或者干脆从字典中说。

我的基本问题是Find total number of unique anagrams in a dictionary?

排序和比较是行不通的，因为它的时间复杂度是非常糟糕的。

我想用哈希表，字符串作为关键的。

但问题是，什么应该是散列函数？如果一些伪提供这将是有益的。一些其他方法除上述方法更好也将是有益的。

谢谢。

Answer 1:

显而易见的解决方案是将每个字符的素数映射和繁殖的素数。因此，如果 'A'” - > 2和 'b' - > 3，则

'AB' - > 6
'' - > 6
文件夹 - > 18
'阿巴' - > 36
'巴巴' - > 36

为了尽量减少溢出的机会，最小素数可分配给更频繁的字母（E，T，I，A，N）。注：第26届总理是101。

UPDATE：实现可以在这里找到

Answer 2:

一个可能的散列函数可以（假设只有英文单词），每个字母出现的次数排序的计数。因此，对于 “字谜” 你会生成[（ '一个'，3），（ 'G'，1），（ 'N'，1），（ 'M'，1），（ 'R'，1）]。

或者，也可以通过（“a”到到第25位representining“Z”位0表示）从字其中对于比特0-25的每个比特表示该字母的存在或不存在产生的位掩码得到不精确的分组。但你不得不做一点更多的处理拆分每个散列组进一步从“太”区分，例如“到”。

请执行这些想法帮助吗？考虑任何特定的实现语言（我可以做C ++，Python或斯卡拉）？

编辑：添加了一些示例Scala代码和输出：

OK：我在此刻Scala的模式，所以我敲东西了，做你问什么，但（啊哈），如果你不那么熟悉斯卡拉或函数式编程它可能不是很清楚。

利用从这里英语单词的大名单： http://scrapmaker.com/data/wordlists/twelve-dicts/2of12.txt

我对它们运行此Scala代码（在脚本模式下使用的Scala 2.9，包括时间进行编译，与约40000字的字典大约需要5秒钟。不是最有效的代码，但浮现在脑海的第一件事）。

// Hashing function to go from a word to a sorted list of letter counts
def toHash(b:String) = b.groupBy(x=>x).map(v => (v._1, v._2.size) ).toList.sortWith(_._1 < _._1)


// Read all words from file, one word per line
val lines = scala.io.Source.fromFile("2of12.txt").getLines

// Go from list of words to list of (hashed word, word)
val hashed = lines.map( l => (toHash(l), l) ).toList

// Group all the words by hash (hence group all anagrams together)
val grouped = hashed.groupBy( x => x._1 ).map( els => (els._1, els._2.map(_._2)) )

// Sort the resultant anagram sets so the largest come first
val sorted = grouped.toList.sortWith( _._2.size > _._2.size )

for ( set <- sorted.slice(0, 10) )
{
    println( set._2 )
}

此转储出所述第一10套字谜（套与大多数成员第一）之中的：

List(caret, cater, crate, react, trace)
List(reins, resin, rinse, risen, siren)
List(luster, result, rustle, sutler, ulster)
List(astir, sitar, stair, stria, tarsi)
List(latrine, ratline, reliant, retinal)
List(caper, crape, pacer, recap)
List(merit, miter, remit, timer)
List(notes, onset, steno, stone)
List(lair, liar, lira, rail)
List(drawer, redraw, reward, warder)

请注意，这里使用的第一个建议（字母数的列表）而不是更复杂的方法掩码。

编辑2：您可以在每个字（如联合申诉委员会的建议）的字符一个简单的排序代替散列函数，并得到更清晰的/更快的代码相同的结果：

def toHash(b:String) = b.toList.sortWith(_<_)

Answer 3:

如果您XOR每个字符的哈希码值，然后通过XOR输入长度的结果，你将得到相同的值，而不管这个词的顺序，这意味着所有字谜游戏会产生相同的哈希值。（异或由长度防止“老板”和“博”从返回相同的值，因为“s”的自相的哈希始终为0）

例：

int AnagramHash(string input)
{
    int output = 0;

    foreach(char c in input)
        output ^= c.GetHashCode();

    return output ^ input.Length;
}

你仍然将不得不寻找具有相同AnagramHash所有单词。我会更新字典表与哈希场（不管你的算法），以降低整体的计算。

编辑：另外，作为一个侧面说明，XOR是由ALU执行的，所以如果你最终使用它，你应该能够很快生成你哈希的最简单的操作。