Алгоритм генерации анаграмм

Question

Какова была бы лучшая стратегия для генерации анаграмм.

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.

• Одиннадцать плюс два - анаграмма Двенадцать плюс один
• Десятичная точка является анаграммой Я на месте
• Астрономы - анаграмма Лунных звезд

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

Я наткнулся на эту страницу, Решение анаграмм в Ruby .

Но каковы ваши идеи?

Answer 1

Пару месяцев назад я использовал следующий способ вычисления анаграмм:

• Вычислите «код» для каждого слова в вашем словаре: создайте справочную таблицу из букв алфавита в простые числа, например, начиная с ['a', 2] и заканчивая ['z', 101]. В качестве шага предварительной обработки вычислите код для каждого слова в вашем словаре, ища простое число для каждой буквы, из которой оно состоит, в таблице соответствия и умножьте их вместе. Для последующего поиска создайте мультикарту кодов для слов.

• Вычислить код вашего входного слова, как указано выше.

• Вычисляет codeInDictionary% inputCode для каждого кода в мультикарте. Если результат равен 0, вы нашли анаграмму и можете найти соответствующее слово. Это также работает для анаграмм из 2 или более слов.

Надеюсь, это было полезно.

Answer 2

Как я это вижу:

вы хотите создать таблицу, которая отображает неупорядоченные наборы букв в списки слов, т. Е. Пройти по словарю, чтобы вы могли, скажем,

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

затем из начального слова вы найдете набор букв:

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

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

edit: хм, это почти то, что написал Джейсон Коэн.

edit: более того, в комментариях к вопросу упоминается генерация «хороших» анаграмм, как в примерах :). после того, как вы составите список всех возможных анаграмм, запустите их через WordNet и найдите те, которые семантически близки к исходной фразе:)

Answer 3

1. Как предложил Джейсон, подготовьте хеш-таблицу создания словаря с сортировкой слов по алфавиту, а само слово-значение (у вас может быть несколько значений на ключ).
2. Удалите пробелы и отсортируйте запрос, прежде чем искать его.

После этого вам нужно выполнить какой-то рекурсивный, исчерпывающий поиск. Псевдокод очень грубо:

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)

В конце вам нужно перебрать список решений и напечатать слова в каждом подсписке с пробелами между ними. Возможно, вам потребуется распечатать все заказы для этих случаев (например, «Я Сэм» и «Сэм Я» оба решения).

Конечно, я не проверял это, и это подход грубой силы.

Answer 4

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