Алгоритм генерации всех возможных буквенных комбинаций заданной строки до 2 букв

Question

Алгоритм генерации всех возможных буквенных комбинаций заданной строки до 2 букв

Попытка создать решатель Anagram в AS3, как показано здесь:

http://homepage.ntlworld.com/adam.bozon/anagramsolver.htm

У меня проблема с тем, чтобы обернуть свой мозг вокруг генерирования всех возможных комбинаций букв для различных длин строк. Если бы я генерировал перестановки только для фиксированной длины, для меня это не было бы такой проблемой ... но я стремлюсь уменьшить длину строки и получить все возможные перестановки из исходного набора букв для строка с максимальной длиной меньше исходной строки. Например, скажем, я хочу, чтобы длина строки равнялась 2, но у меня есть трехбуквенная строка «abc», результат будет: ab ac ba bc ca cb.

В идеале алгоритм должен был бы создать полный список возможных комбинаций, начиная с исходной длины строки, вплоть до наименьшей длины строки 2. У меня есть ощущение, что, вероятно, есть небольшой рекурсивный алгоритм, чтобы сделать это, но не могу обернуть мой мозг вокруг этого. Я работаю в AS3.

Спасибо!

Answer 1

Для написания решателя анаграмм, который вы связали, запрашиваемый вами алгоритм не нужен. Это также очень дорого.

Давайте посмотрим на 6-буквенное слово, например MONKEY. Все 6 букв слова разные, поэтому вы должны создать:

• 6 * 5 * 4 * 3 * 2 * 1 различных 6-буквенных слов
• 6 * 5 * 4 * 3 * 2 разных пятибуквенных слова
• 6 * 5 * 4 * 3 разных 4-х буквенных слова
• 6 * 5 * 4 разных 3-х буквенных слова
• 6 * 5 разных двухбуквенных слов
• Всего 1950 слов

Теперь, по-видимому, вы не пытаетесь выплевывать все 1950 слов (например, «OEYKMN») в виде анаграмм (которые они есть, но большинство из них также являются бредом). Я предполагаю, что у вас есть словарь юридических английских слов, и вы просто хотите проверить, являются ли какие-либо из этих слов анаграммами слова запроса, с возможностью не использовать все буквы.

Если это так, то проблема проста.

Чтобы определить, являются ли 2 слова анаграммами друг друга, все, что вам нужно сделать, это подсчитать, сколько раз используются каждая буква, и сравнить эти числа!

Давайте ограничимся только 26 буквами A-Z без учета регистра. Вам нужно написать функцию countLetters, которая берет слово и возвращает массив из 26 чисел. Первое число в массиве соответствует счету буквы A в слове, второе число соответствует счету B и т. Д.

Тогда два слова W1 и W2 являются точной анаграммой, если countLetters(W1)[i] == countLetters(W2)[i] для каждого i! То есть каждое слово использует каждую букву одинаковое количество раз!

Для того, что я бы назвал поданаграммами (MONEY - это поданаграмма MONKEY), W1 - это поданаграмма W2, если countLetters(W1)[i] <= countLetters(W2)[i] для каждого i! То есть в поданаграмме может использоваться меньше определенных букв, но не больше!

(примечание: MONKEY также является поданаграммой MONKEY).

---

Это должно дать вам достаточно быстрый алгоритм, при котором для заданной строки запроса все, что вам нужно сделать, - это один раз прочитать словарь, сравнив массив букв каждого слова с массивом букв слова запроса. Вы можете сделать небольшую оптимизацию, но этого должно быть достаточно.

В качестве альтернативы, если вам нужна максимальная производительность, вы можете предварительно обработать словарь (который известен заранее) и создать ориентированный ациклический граф взаимосвязи поданаграмм.

Вот часть такого графика для иллюстрации:

 D=1,G=1,O=1  ----------> D=1,O=1
  {dog,god}   \            {do,od}
               \
                \-------> G=1,O=1
                           {go}

По сути, каждый узел является корзиной для всех слов, имеющих одинаковый массив букв (т.е. они являются точными анаграммами). Тогда есть узел от N1 до N2, если массив N2 равен <= (как определено выше) N1 массив (вы можете выполнить переходное сокращение, чтобы сохранить наименьшее количество ребер).

Затем, чтобы составить список всех поданаграмм слова, все, что вам нужно сделать, это найти узел, соответствующий его массиву счетчиков букв, и рекурсивно исследовать все узлы, доступные из этого узла. Все их ведра содержат субанаграммы.

Answer 2

Следующий код js найдет все возможные «слова» в n буквенном слове. Конечно, это не значит, что это настоящие слова, но дает вам все комбинации. На моей машине это занимает около 0,4 секунды для 7-буквенного слова и 15 секунд для 9-буквенного слова (почти до миллиона возможностей, если нет повторяющихся букв). Однако эти времена включают поиск в словаре и поиск настоящих слов.

var getWordsNew=function(masterword){
var result={}
 var a,i,l;
function nextLetter(a,l,key,used){
     var i;
    var j;
    if(key.length==l){
        return;
    }
    for(i=0;i<l;i++){
        if(used.indexOf(""+i)<0){
            result[key+a[i]]="";
            nextLetter(a,l,key+a[i],used+i);
        }
    }
 }
a=masterword.split("");
  l=a.length;
for (i = 0; i < a.length; i++) {
    result[a[i]] = "";
    nextLetter(a, l, a[i], "" + i)
}
return result;
}

Полный код на

Код для поиска слов в словах

Answer 3

Существует простой O (N), где n - размер словаря. Просто отсортируйте буквы в каждом слове в словаре или лучше, создайте двоичную маску из них, а затем сравните те буквы, которые у вас есть.

Answer 4

Вы можете генерировать все слова в алфавите, находя все пути в полном графике букв. Вы можете найти все пути в этом графике, выполнив поиск в глубину по каждой букве и вернув текущий путь в каждой точке.

Answer 5

Вы хотите что-то вроде договоренностей. Если вы знакомы с алгоритмом перестановки, значит, у вас есть проверка, чтобы увидеть, когда вы сгенерировали достаточно чисел. Просто измените этот предел:

Я не знаю 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);