生成变位词的最佳策略是什么？
起初看起来很简单，只需混淆字母并生成所有可能的组合。但是如何高效地生成字典中的单词呢？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
这些回答大多效率低下，或者只能给出单词解决方案（没有空格）。 我的解决方案可以处理任意数量的单词，并且非常高效。
你需要使用 trie 数据结构。这里有一个完整的 Python 实现。你只需要将单词列表保存在名为 words.txt 的文件中。你可以在这里尝试 Scrabble 字典单词列表：
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()
if子句来修复此问题，但我必须把这个任务留给懂Python的人。 - Martin J.H.对于字典中的每个单词，按字母顺序排序。因此，“foobar”变为“abfoor”。
然后输入乱序单词时，也要将其字母排序，然后查找字典。它就像哈希表一样快！
对于多个单词，可以通过组合排序后的字母来进行搜索，同时在排序过程中进行排序。仍然比生成所有组合要快得多。
（有关更多优化和详细信息，请参见注释）
预处理：
构建一棵字典树，每个叶子节点表示一个已知单词，按照字母顺序进行键入。
搜索时：
将输入字符串视为一个多重集合。通过深度优先搜索遍历索引字典树以查找第一个子单词。在每个分支处，您可以询问：我的输入剩余部分中是否包含字母x？如果您有一个良好的多重集合表示，这应该是一个常数时间查询（基本上）。
一旦您获得了第一个子单词，您可以保留剩余的多重集合，并将其视为查找该变位词的其余部分的新输入（如果存在）。
使用备忘录增强此过程，以便更快地查找常见的剩余多重集合。
这很快 - 每次字典树遍历都保证给出一个实际的子单词，并且每次遍历的时间复杂度与子单词长度成线性关系（通过编码标准，子单词通常非常小）。但是，如果您真的想要更快的速度，您可以在预处理中包含所有n-gram，其中n-gram是任何连续n个单词的字符串。当然，如果W =＃单词，则索引大小将从O（W）跳至O（W ^ n）。根据您的字典大小，n = 2可能是现实的。
以下是 Jason Cohen 建议的 Java 工作解决方案，它的表现比使用 trie 的解决方案要好一些。以下是一些主要要点：
以下是找到变位词键集合的主递归代码：
// recursive function to find all the anagrams for charInventory characters
// starting with the word at dictionaryIndex in dictionary keyList
private Set<Set<String>> findAnagrams(int dictionaryIndex, char[] charInventory, List<String> keyList) {
// terminating condition if no words are found
if (dictionaryIndex >= keyList.size() || charInventory.length < minWordSize) {
return null;
}
String searchWord = keyList.get(dictionaryIndex);
char[] searchWordChars = searchWord.toCharArray();
// this is where you find the anagrams for whole word
if (AnagramSolverHelper.isEquivalent(searchWordChars, charInventory)) {
Set<Set<String>> anagramsSet = new HashSet<Set<String>>();
Set<String> anagramSet = new HashSet<String>();
anagramSet.add(searchWord);
anagramsSet.add(anagramSet);
return anagramsSet;
}
// this is where you find the anagrams with multiple words
if (AnagramSolverHelper.isSubset(searchWordChars, charInventory)) {
// update charInventory by removing the characters of the search
// word as it is subset of characters for the anagram search word
char[] newCharInventory = AnagramSolverHelper.setDifference(charInventory, searchWordChars);
if (newCharInventory.length >= minWordSize) {
Set<Set<String>> anagramsSet = new HashSet<Set<String>>();
for (int index = dictionaryIndex + 1; index < keyList.size(); index++) {
Set<Set<String>> searchWordAnagramsKeysSet = findAnagrams(index, newCharInventory, keyList);
if (searchWordAnagramsKeysSet != null) {
Set<Set<String>> mergedSets = mergeWordToSets(searchWord, searchWordAnagramsKeysSet);
anagramsSet.addAll(mergedSets);
}
}
return anagramsSet.isEmpty() ? null : anagramsSet;
}
}
// no anagrams found for current word
return null;
}
这里是我新颖的解决方案，点击此处。
Jon Bentley的《Programming Pearls》中有一道关于查找单词的变位词（anagrams）问题。
给定一个包含英文单词的字典，查找所有的变位词。例如，“pots”，“stop”和“tops”都是相互变位词，因为每个单词都可以通过重新排列字母来形成另一个单词。
我思考了一下，发现可以通过获得要搜索单词的签名，并将其与字典中的所有单词进行比较来解决该问题。所有单词的变位词应该具有相同的签名。但如何实现呢？我的想法是使用算术基本定理：
算术基本定理规定：
每个正整数（除了数字1）都可以表示为一个或多个质数的积，且唯一。
因此，我们可以使用前26个质数的数组。对于单词中的每个字母，我们获取相应的质数，例如A = 2，B = 3，C = 5，D = 7...然后计算输入单词的乘积。接下来，我们对字典中的每个单词都进行这样的计算，如果一个单词与输入单词匹配，则将其添加到结果列表中。
性能相当可观。对于一个包含479828个单词的字典，获取所有变位词需要160毫秒。这大约是每个单词0.0003毫秒，或者每个单词0.3微秒。该算法的复杂度似乎为O(mn)或~O(m)，其中m为字典的大小，n为输入单词的长度。
以下是代码：
package com.vvirlan;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Scanner;
public class Words {
private int[] PRIMES = new int[] { 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, 103, 107, 109, 113 };
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
String word = "hello";
System.out.println("Please type a word:");
if (s.hasNext()) {
word = s.next();
}
Words w = new Words();
w.start(word);
}
private void start(String word) {
measureTime();
char[] letters = word.toUpperCase().toCharArray();
long searchProduct = calculateProduct(letters);
System.out.println(searchProduct);
try {
findByProduct(searchProduct);
} catch (Exception e) {
e.printStackTrace();
}
measureTime();
System.out.println(matchingWords);
System.out.println("Total time: " + time);
}
private List<String> matchingWords = new ArrayList<>();
private void findByProduct(long searchProduct) throws IOException {
File f = new File("/usr/share/dict/words");
FileReader fr = new FileReader(f);
BufferedReader br = new BufferedReader(fr);
String line = null;
while ((line = br.readLine()) != null) {
char[] letters = line.toUpperCase().toCharArray();
long p = calculateProduct(letters);
if (p == -1) {
continue;
}
if (p == searchProduct) {
matchingWords.add(line);
}
}
br.close();
}
private long calculateProduct(char[] letters) {
long result = 1L;
for (char c : letters) {
if (c < 65) {
return -1;
}
int pos = c - 65;
result *= PRIMES[pos];
}
return result;
}
private long time = 0L;
private void measureTime() {
long t = new Date().getTime();
if (time == 0L) {
time = t;
} else {
time = t - time;
}
}
}
几个月前，我使用以下的方式计算字谜：
为字典中的每一个单词计算一个“代码”：创建从字母到质数的查找表，例如以 ['a'，2] 开始以 ['z'，101] 结束。作为预处理步骤，通过在查找表中查找它所组成的每个字母的质数来计算字典中每个单词的代码，并将它们相乘。为了进行后续查询，创建代码映射到单词的多重映射。
按照上述方式计算输入单词的代码。
对于多重映射中的每个代码，计算 codeInDictionary % inputCode。如果结果为 0，则已经找到一个字谜，可以查找相应的单词。这也适用于由两个或多个单词组成的字谜。
希望这有所帮助。
Programming Pearls这本书是Jon Bentley写的，非常好地涵盖了这种东西。必读。
我的看法是：
你需要构建一个将无序字母集映射到单词列表的表格，即遍历字典，这样你就会得到，比如说：
lettermap[set(a,e,d,f)] = { "deaf", "fade" }
然后从您的起始单词开始，找到字母集：
astronomers => (a,e,m,n,o,o,r,r,s,s,t)
然后循环遍历该集合的所有分区（这可能是最技术性的部分，只需生成所有可能的分区），并查找该字母集的单词。
编辑：嗯，这基本上就是Jason Cohen发布的内容。
编辑：此外，问题的评论提到生成“好”的变位词，例如示例 :). 在构建了所有可能的变位词列表之后，运行它们通过WordNet并找到与原始短语在语义上接近的词汇 :)