生成字谜的最佳策略是什么？

An anagram is a type of word play, the result of rearranging the letters
of a word or phrase to produce a new  word or phrase, using all the original
letters exactly once; 
ex.

  
  
  Eleven plus two is anagram of Twelve plus one 
  A decimal point is anagram of I'm a dot in place
  Astronomers is anagram of Moon starers

乍一看，它看起来很简单，只是弄乱字母并生成所有可能的组合。但是，仅生成词典中单词的有效方法是什么。

我碰到了这个页面，用Ruby解决字谜。

但是你有什么想法？

解决方案

回答

在我脑海中，最有意义的解决方案是从输入字符串中随机选择一个字母，然后根据以此开头的单词过滤字典。然后选择另一个，过滤第二个字母，依此类推。此外，过滤掉无法用其余文本制成的单词。然后，当我们敲一个单词的末尾时，插入一个空格，然后从其余字母开始。我们可能还会根据字词类型限制字词(例如，我们不会有两个相邻的动词，我们不会有两个相邻的文章，等等)。

回答

对于字典中的每个单词，请按字母顺序对字母进行排序。因此，" foobar"变成了"笨蛋"。

然后，当输入字谜出现时，也将其字母排序，然后查找。它与哈希表查找一样快！

对于多个单词，我们可以对已排序的字母进行组合，然后再进行排序。仍然比生成所有组合要快得多。

(请参阅注释以获取更多优化和详细信息)

回答

我怎么看：

我们想建立一个表格，将无序的字母集映射到列出的单词，即通过字典，这样我们就可以说出

lettermap[set(a,e,d,f)] = { "deaf", "fade" }

然后从起始单词中找到一组字母：

astronomers => (a,e,m,n,o,o,r,r,s,s,t)

然后遍历该集合的所有分区(这可能是最技术性的部分，只是生成所有可能的分区)，并查找该字母集合的单词。

编辑：嗯，这差不多是杰森·科恩(Jason Cohen)发布的内容。

编辑：此外，对问题的评论提到生成"好"字谜，如示例:)。在建立了所有可能的七字组的列表之后，通过WordNet运行它们，并找到在语义上与原始短语接近的词组:)

回答

• 正如Jason所建议的那样，准备一个字典制作哈希表，其中的键是按字母顺序对单词进行排序的单词，并且值单词本身(每个键可能有多个值)。
• 删除空格并在查询之前对查询进行排序。

之后，我们需要进行某种递归，详尽的搜索。伪代码非常粗略：

function FindWords(solutionList, wordsSoFar, sortedQuery)
  // base case
  if sortedQuery is empty
     solutionList.Add(wordsSoFar)
     return

  // recursive case

  // InitialStrings("abc") is {"a","ab","abc"}
  foreach initialStr in InitalStrings(sortedQuery)
    // Remaining letters after initialStr
    sortedQueryRec := sortedQuery.Substring(initialStr.Length)
    words := words matching initialStr in the dictionary
    // Note that sometimes words list will be empty
    foreach word in words
      // Append should return a new list, not change wordSoFar
      wordsSoFarRec := Append(wordSoFar, word) 
      FindWords(solutionList, wordSoFarRec, sortedQueryRec)

最后，我们需要遍历solutionList，并打印每个子列表中的单词，并在它们之间留有空格。我们可能需要针对这些情况打印所有订单(例如，"我是Sam"和" Sam我是"都是解决方案)。

当然，我没有对此进行测试，这是一种蛮力的方法。

回答

请参阅华盛顿大学CSE系的作业。

基本上，我们有一个仅包含单词中每个字母的计数的数据结构(数组适用于ascii，如果我们要支持unicode，请升级到地图)。我们可以减去其中两个字母集；如果计数为负，则我们知道一个单词不能是另一个单词的字谜。

回答

预处理：

用字母顺序将每个叶子作为一个已知单词构建一个trie。

在搜索时：

将输入字符串视为多集。如深度优先搜索中那样遍历索引来找到第一个子词。在每个分支机构，我们都可以问，我输入的其余部分中的字母x是吗？如果我们具有良好的多集表示形式，则这应该是一个恒定时间的查询(基本上)。

一旦有了第一个子词，就可以保留其余的多集并将其作为新输入来查找该字谜的其余部分(如果存在)。

通过记忆扩展此过程，以便更快地查找常见余数多集。

保证每个特里遍历都可以给出一个实际的子字，这是非常快的，并且每次遍历在子字的长度上花费线性时间(根据编码标准，子字通常很小)。但是，如果我们真的想要更快的速度，则可以在预处理过程中包括所有n-gram，其中n-gram是连续n个单词的任何字符串。当然，如果W = #words，那么我们将从索引大小O(W)跳到O(W ^ n)。也许n = 2是现实的，具体取决于字典的大小。

回答

两个月前，我使用了以下方法来计算字谜：

• 为字典中的每个单词计算一个"代码"：创建一个查找表，从字母表中的字母到质数，例如以['a'，2]开头，以['z'，101]结尾。作为预处理步骤，通过在查找表中查找包含在每个字母中的每个字母的质数并将它们相乘，来计算字典中每个单词的代码。对于以后的查找，请创建一个代码到单词的多重映射。
• 如上所述，计算输入单词的代码。
• 计算multimap中每个代码的codeInDictionary％inputCode。如果结果为0，则说明我们找到了一个字谜，可以查找适当的单词。这也适用于2字或者更多字的字谜。

希望对我们有所帮助。

回答

乔恩·本特利(Jon Bentley)的《编程珍珠》(Programming Pearls)一书很好地涵盖了这类内容。必读。

回答

不久前，我写了一篇博客文章，介绍如何快速找到两个词字谜。它的工作速度非常快：在Ruby程序中，为一个文本文件超过300,000个单词(4兆字节)的单词找到所有44个两个单词的字谜都只需0.6秒。

两词字谜查找器算法(在Ruby中)

当允许将单词表预处理成大的散列映射(从按字母排序的单词到使用这些字母的单词列表)时，可以使应用程序更快。此后的数据可以序列化并从那时开始使用。

回答

关于程序七巧板的开创性著作之一是迈克尔·莫顿(Mr. Machine Tool)，他使用的是称为Ars Magna的工具。这是根据他的工作写的一篇简短的文章。

回答

这些答案大多数效率极低，并且/或者只能给出一个单词的解决方案(无空格)。我的解决方案可以处理任意数量的单词，并且非常有效。

我们想要的是trie数据结构。这是一个完整的Python实现。我们只需要将单词表保存在名为words.txt的文件中，就可以在此处尝试拼字词典单词表：

http://www.isc.ro/lists/twl06.zip

MIN_WORD_SIZE = 4 # min size of a word in the output

class Node(object):
    def __init__(self, letter='', final=False, depth=0):
        self.letter = letter
        self.final = final
        self.depth = depth
        self.children = {}
    def add(self, letters):
        node = self
        for index, letter in enumerate(letters):
            if letter not in node.children:
                node.children[letter] = Node(letter, index==len(letters)-1, index+1)
            node = node.children[letter]
    def anagram(self, letters):
        tiles = {}
        for letter in letters:
            tiles[letter] = tiles.get(letter, 0) + 1
        min_length = len(letters)
        return self._anagram(tiles, [], self, min_length)
    def _anagram(self, tiles, path, root, min_length):
        if self.final and self.depth >= MIN_WORD_SIZE:
            word = ''.join(path)
            length = len(word.replace(' ', ''))
            if length >= min_length:
                yield word
            path.append(' ')
            for word in root._anagram(tiles, path, root, min_length):
                yield word
            path.pop()
        for letter, node in self.children.iteritems():
            count = tiles.get(letter, 0)
            if count == 0:
                continue
            tiles[letter] = count - 1
            path.append(letter)
            for word in node._anagram(tiles, path, root, min_length):
                yield word
            path.pop()
            tiles[letter] = count

def load_dictionary(path):
    result = Node()
    for line in open(path, 'r'):
        word = line.strip().lower()
        result.add(word)
    return result

def main():
    print 'Loading word list.'
    words = load_dictionary('words.txt')
    while True:
        letters = raw_input('Enter letters: ')
        letters = letters.lower()
        letters = letters.replace(' ', '')
        if not letters:
            break
        count = 0
        for word in words.anagram(letters):
            print word
            count += 1
        print '%d results.' % count

if __name__ == '__main__':
    main()

当我们运行该程序时，这些单词将被加载到内存中的trie中。之后，只需输入要搜索的字母，它就会打印结果。它只会显示使用所有输入字母的结果，不要再短了。

它从输出中过滤掉简短的单词，否则结果的数量很大。随时调整" MIN_WORD_SIZE"设置。请记住，如果" MIN_WORD_SIZE"为1，仅使用" astronomers"作为输入将得到233,549结果。也许我们会找到一个较短的单词列表，其中仅包含更常见的英语单词。

同样，除非我们在字典中添加" im"并将" MIN_WORD_SIZE"设置为2，否则收缩" I'm"(来自示例之一)不会出现在结果中。

获取多个单词的技巧是，每当我们在搜索中遇到一个完整的单词时，都将跳回到该树的根节点。然后，我们将继续遍历trie，直到所有字母都被使用。