Алгоритм для генерации всех возможных сочетаний букв данной строки вниз к 2 буквам
Алгоритм для генерации всех возможных сочетаний букв данной строки вниз к 2 буквам
Пытаться создать решатель Анаграммы в AS3, таком как этот нашло здесь:
http://homepage.ntlworld.com/adam.bozon/anagramsolver.htm
У меня есть проблема при обертывании моего мозга вокруг генерации всех возможных сочетаний букв для различных длин строк. Если бы я только генерировал перестановки для фиксированной длины, то это не была бы такая проблема для меня..., но я надеюсь уменьшать длину строки и получать все возможные перестановки из исходного набора букв для строки с макс. длиной, меньшей, чем исходная строка. Например, скажите, что я хочу длину строки 2, все же у меня есть 3 буквенных строки “abc”, вывод был бы: ab ac ba до н.э приблизительно cb.
Идеально алгоритм произвел бы полный список возможных комбинаций, запускающихся с длины исходной строки, вниз к наименьшей длине строки 2. У меня есть чувство, что существует, вероятно, небольшой рекурсивный алгоритм, чтобы сделать это, но не может перенести мой мозг вокруг этого. Я работаю в AS3.
Спасибо!
4 ответа
Для написания решателя анаграмм, тип которого вы связали, запрашиваемый алгоритм не нужен. К тому же это ОЧЕНЬ дорого.
Рассмотрим, например, слово из 6 букв, такое как ОБЕЗЬЯНА . Все 6 букв в слове разные, поэтому вы должны создать:
- 6 * 5 * 4 * 3 * 2 * 1 разных 6-буквенных слов
- 6 * 5 * 4 * 3 * 2 разных 5-буквенных слова
- 6 * 5 * 4 * 3 разных слова из 4 букв
- 6 * 5 * 4 разных слова из 3 букв
- 6 * 5 разных слов из 2 букв
- Всего 1950 слов
Теперь, по-видимому, вы не пытаетесь выплюнуть все 1950 слов (например,«ОЭЙКМН») как анаграммы (что они и есть, но большинство из них также являются тарабарщиной). Я предполагаю, что у вас есть словарь юридических английских слов, и вы просто хотите проверить, не являются ли какие-либо из этих слов анаграммами слова запроса, с возможностью не использовать все буквы.
Если это так, то проблема проста.
Чтобы определить, являются ли 2 слова анаграммами друг друга, все, что вам нужно сделать, это посчитать, сколько раз используется каждая буква, и сравнить эти числа!
Давайте ограничимся 26 буквами A – Z без учета регистра. Что вам нужно сделать, так это написать функцию countLetters , которая принимает слово и возвращает массив из 26 чисел. Первое число в массиве соответствует числу букв A в слове, второе число соответствует числу B и т. Д.
Затем два слова W1 и W2 являются точными анаграммами, если countLetters (W1) [i] == countLetters (W2) [i] для каждого i ! То есть каждое слово использует каждую букву одинаковое количество раз!
Для того, что я бы назвал субанаграммой ( ДЕНЬГИ - субанаграмма ОБЕЗЬЯНА ), W1 является субанаграммой ] W2 если countLetters (W1) [i] <= countLetters (W2) [i] для каждого i ! То есть субанаграмма может использовать меньше определенных букв, но не больше!
(примечание: ОБЕЗЬЯНА также является субанаграммой для ОБЕЗЬЯНЫ ).
Это должно дать вам достаточно быстрый алгоритм, в котором для заданной строки запроса все, что вам нужно сделать, это прочитать словарь один раз, сравнивая массив подсчета букв каждого слова с массивом подсчета букв слова запроса. Вы можете сделать небольшую оптимизацию, но этого должно быть достаточно.
В качестве альтернативы, если вам нужна максимальная производительность, вы можете предварительно обработать словарь (который известен заранее) и создать направленный ациклический граф взаимосвязи субанаграмм.
Вот часть такого графика для иллюстрации:
D=1,G=1,O=1 ----------> D=1,O=1
{dog,god} \ {do,od}
\
\-------> G=1,O=1
{go}
По сути, каждый узел - это корзина для всех слов, которые имеют один и тот же массив подсчета букв (т.е. они точные анаграммы). Затем существует узел от N1 до N2 , если массив N2 равен <= (как определено выше) N1 (можно выполнить транзитивное сокращение, чтобы сохранить наименьшее количество ребер).
Затем, чтобы перечислить все субанаграммы слова, все, что вам нужно сделать, это найти узел, соответствующий его массиву подсчета букв, и рекурсивно исследовать все узлы, доступные из этого узла. Все их корзины будут содержать поданаграммы.
Вы можете сгенерировать все слова в алфавите, найдя все пути в полном графике букв. Вы можете найти все пути на этом графике, выполняя поиск в глубину для каждой буквы и возвращая текущий путь в каждой точке.
Вы хотите своего рода аранжировки. Если вы знакомы с алгоритмом перестановки, то знаете, что у вас есть проверка, чтобы увидеть, когда вы сгенерировали достаточно чисел. Просто измените это ограничение:
Я не знаю AS3, но вот псевдокод:
st = an array
Arrangements(LettersInYourWord, MinimumLettersInArrangement, k = 1)
if ( k > MinimumLettersInArrangements )
{
print st;
}
if ( k > LettersInYourWord )
return;
for ( each position i in your word that hasn't been used before )
st[k] = YourWord[i];
Arrangements(<same>, <same>, k + 1);
для «abc» и Arrangements (3, 2, 1); это напечатает:
ab
abc
ac
acb
...
Если вы хотите сначала те, у которых три, а затем те, у которых два, примите во внимание следующее:
st = an array
Arrangements(LettersInYourWord, DesiredLettersInArrangement, k = 1)
if ( k > DesiredLettersInArrangements )
{
print st;
return
}
for ( each position i in your word that hasn't been used before )
st[k] = YourWord[i];
Arrangements(<same>, <same>, k + 1);
Затем для вызова «abc» Arrangements (3, 3, 1); а затем Arrangements (3, 2, 1);
Есть простое O (N), где n - размер словаря. Просто отсортируйте буквы в каждом слове словаря или лучше, создайте из них двоичную маску, а затем сравните имеющиеся у вас буквы.