Алгоритм для нахождения самой длинной анаграммы
Подрывная деятельность была бы вид работы. См. поток
Лично, я предпочитаю сохранять все на единственной машине и Удаленном рабочем столе в нее.
5 ответов
Я бы пошел с немного измененной версией ответа на вопрос об анаграмме здесь
Для каждого слова в словаре отсортируйте буквы в алфавитном порядке. Таким образом, "foobar" становится "abfoor".
Начните с вашего полного ввода, отсортированного в алфавитном порядке. Если не найдено, удалите одну букву, повторите поиск. Сделайте это для каждой буквы. Затем удалите две буквы ... и т. Д.
Худший случай: «анаграммы» вообще не найдено. Вам нужно будет протестировать все возможные комбинации ввода, что даст вам около 2 ^ n поисков, где n - количество входных символов (в вашем примере: 12) Однако скорость работы алгоритма не зависит от размера словаря во время выполнения (конечно, сортировка слов по алфавиту зависит), что, на мой взгляд, здесь наиболее важно.
Вы должны вычислить подпись каждого слова, вы делаете это только один раз и сохраняете ее в своей базе данных вместе со словом.
Таблица должна быть примерно такой:
word varchar(12),
a int,
b int,
c int,
...
w int,
z int;
и поля от a до z должны содержать количество букв, содержащихся в слове, например, анаграмма будет иметь такую запись:
word, a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
anagram, 3,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0
как только у вас есть двенадцать букв, вам нужно вычислить подпись набора и использовать ее для создания подобного выбора:
select word, length(word) as wordlen
from dictionary
where
a <= 4 and
b <= 0 and
c <= 1 and
d <= 2 and
e <= 0 and
f <= 0 and
....
z <= 0
order by wordlen desc;
, чтобы иметь все слова, которые могут быть созданы с использованием имеющегося у вас набора букв.
Никаких перестановок, никаких комбинаций и хотя работа (составление словаря) не выполняется только один раз и офлайн.
Еще один совет: удалите из базы данных все слова, длина которых превышает двенадцать символов
Если вы пытаетесь найти самое длинное совпадающее слово, я бы начал с попытки отсортировать словарь по длине слова, чтобы вы могли сосредоточить больше усилий на самых длинных словах
Моя идея:
псевдокод:
int_32 letter_mask
int_32 permutation_match_mask
if(((letter_mask XOR permutation_match_mask) AND letter_mask) == 0)
YOU_HAVE_HIT;
хорошо, это работает, когда у вас есть неповторяющиеся буквы в маске букв, но если у вас больше букв (а у вас, вероятно, есть), вы можете расширить букву и маска совпадения перестановок
РЕДАКТИРОВАТЬ
Другая идея
Сортировка слов в словаре в алфавитном порядке.
если букв 12 и все они разные, то имеется ровно 4095 возможных сочетаний (просто сумма i = 1 -> 12 биномиальных (12 над i)) (для букв ABCD есть (ABCD, ABC, ABD, ACD, BCD, AB, AC, AD, BC, BD, CD, A, B, C, D) И как Я сказал, что есть 4095 в 12 разных буквах и даже меньше, если некоторые буквы совпадают.
Сложность 4095 * Log2 (250000), что примерно равно 75000. Что ж, стоит попробовать.
Пойдите для точного поиска по каждой комбинация.
Eric Lippert has written an informative blog post about anagram searching. The examples all use c#, but the techniques are usable in any language.
The trick to efficiently searching for anagrams in a dictionary is to realize that all anagrams have the same letters, just in different order. If you "canonicalize" each word so that its letters are uppercase and in alphabetical order, then checking whether one word is an anagram of another is as simple as comparing their canonical forms
With this technique, you can easily look up anagrams from a hash table or balanced tree.