Алгоритм для получения списка всех слов, которые являются анаграммами всех подстрок (scrabble)?

Ответ 1

Структура, используемая для хранения словаря действительных записей, будет иметь огромное влияние на эффективность. Организуйте его как дерево, корень - единственное "слово" нулевой буквы, пустая строка. Каждый корень корня является единственной первой буквой возможного слова, дети из которых являются второй буквой возможного слова и т.д., Причем каждый node помечен как он на самом деле образует слово или нет.

Функция вашего тестера будет рекурсивной. Он начинается с нулевых букв, находит из дерева допустимых записей, что "" не является словом, но у него есть дети, поэтому вы рекурсивно вызываете своего тестера с вашим стартовым словом (без букв), прилагаемым к каждому доступному оставшемуся письму с вашего входной строки (которая является их всем в этой точке). Проверяйте каждую однобуквенную запись в дереве, если она действительна; если дети, функция повторного вызова тестера, добавляющая каждую оставшуюся доступную букву и т.д.

Итак, например, если ваша строка ввода "helloworld", вы сначала вызовите функцию рекурсивного тестера с помощью "", передав оставшиеся доступные буквы "helloworld" в качестве второго параметра. Функция видит, что " "не является словом, но существует дочерний" h ". Таким образом, он называет себя" h "и" celloworld ". Функция видит, что" h "не является словом, но существует дочернее" e ". Поэтому он называет себя" он "и" светлый мир ". Функция видит, что" e "отмечено, поэтому" он "- это слово, обратите внимание. Кроме того, существует дочерний" l ", поэтому следующий вызов" hel "с" loworld ". Затем он найдет" ад ", затем" привет ", затем придется отступить и, вероятно, затем найти" пустоту ", прежде чем снова вернуться к пустой строке, а затем начать с следующих слов" e".

Ответ 2

Я не мог устоять перед своей собственной реализацией. Он создает словарь, сортируя все буквы в алфавитном порядке и сопоставляя их со словами, которые могут быть созданы из них. Это операция запуска O (n), которая устраняет необходимость поиска всех перестановок. Вы можете реализовать словарь как trie на другом языке для достижения более быстрого ускорения.

Команда getAnagrams также является операцией O (n), которая ищет каждое слово в словаре, чтобы узнать, является ли это подмножеством поиска. Выполнение getAnagrams ( "radiotelegraphically" ) "(20-буквенное слово) заняло около 1 секунды на моем ноутбуке и вернуло 1496 анаграмм.

# Using the 38617 word dictionary at 
# http://www.cs.umd.edu/class/fall2008/cmsc433/p5/Usr.Dict.Words.txt
# Usage: getAnagrams("helloworld")

def containsLetters(subword, word):
    wordlen = len(word)
    subwordlen = len(subword)

    if subwordlen > wordlen:
        return False

    word = list(word)
    for c in subword:
        try:
            index = word.index(c)
        except ValueError:
            return False
        word.pop(index)
    return True

def getAnagrams(word):
    output = []
    for key in mydict.iterkeys():
        if containsLetters(key, word):
            output.extend(mydict[key])

    output.sort(key=len)
    return output

f = open("dict.txt")
wordlist = f.readlines()
f.close()

mydict = {}
for word in wordlist:
    word = word.rstrip()
    temp = list(word)
    temp.sort()
    letters = ''.join(temp)

    if letters in mydict:
        mydict[letters].append(word)
    else:
        mydict[letters] = [word]

Пример:

>>> getAnagrams("helloworld")
>>> ['do', 'he', 'we', 're', 'oh', 'or', 'row', 'hew', 'her', 'hoe', 'woo', 'red', 'dew', 'led', 'doe', 'ode', 'low', 'owl', 'rod', 'old', 'how', 'who', 'rho', 'ore', 'roe', 'owe', 'woe', 'hero', 'wood', 'door', 'odor', 'hold', 'well', 'owed', 'dell', 'dole', 'lewd', 'weld', 'doer', 'redo', 'rode', 'howl', 'hole', 'hell', 'drew', 'word', 'roll', 'wore', 'wool','herd', 'held', 'lore', 'role', 'lord', 'doll', 'hood', 'whore', 'rowed', 'wooed', 'whorl', 'world', 'older', 'dowel', 'horde', 'droll', 'drool', 'dwell', 'holed', 'lower', 'hello', 'wooer', 'rodeo', 'whole', 'hollow', 'howler', 'rolled', 'howled', 'holder', 'hollowed']

Ответ 3

Структура данных, которую вы хотите, называется Directed Acyclic Word Graph (dawg), и она описана Эндрю Аппелом и Гаем Якобсеном в их документ "The World Fastest Scrabble Program", который, к сожалению, они решили не предоставлять бесплатные онлайн-игры. Членство ACM или университетская библиотека получат его за вас.

Я реализовал эту структуру данных хотя бы на двух языках - это просто, легко реализовать и очень, очень быстро.

Ответ 4

Что вам нужно - это реализация power set.

Посмотрите также на блог Эрика Липперта, он долгое время писал о это очень немного

EDIT:

Вот реализация, которую я написал о получении синтаксиса из заданной строки...

private IEnumerable<string> GetPowerSet(string letters)
{
  char[] letterArray = letters.ToCharArray();
  for (int i = 0; i < Math.Pow(2.0, letterArray.Length); i++)
  {
    StringBuilder sb = new StringBuilder();
    for (int j = 0; j < letterArray.Length; j++)
    {
      int pos = Convert.ToInt32(Math.Pow(2.0, j));
      if ((pos & i) == pos)
      {
        sb.Append(letterArray[j]);
      }
    }
    yield return new string(sb.ToString().ToCharArray().OrderBy(c => c).ToArray());
  }
}

Эта функция дает мне полномочия символов, которые составляют переданную в строке, тогда я могу использовать их как ключи в словаре анаграмм...

Dictionary<string,IEnumerable<string>>

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

wordlist = (from s in fileText.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries)
                let k = new string(s.ToCharArray().OrderBy(c => c).ToArray())
                group s by k).ToDictionary(o => o.Key, sl => sl.Select(a => a));

Ответ 5

Простой подход состоит в том, чтобы сгенерировать все "подстроки" и, для каждого из них, проверить, является ли он элементом набора допустимых слов. Например, в Python 2.6:

import itertools
import urllib

def words():
  f = urllib.urlopen(
    'http://www.cs.umd.edu/class/fall2008/cmsc433/p5/Usr.Dict.Words.txt')
  allwords = set(w[:-1] for w in f)
  f.close()
  return allwords

def substrings(s):
  for i in range(2, len(s)+1):
    for p in itertools.permutations(s, i):
      yield ''.join(p)

def main():
  w = words()
  print '%d words' % len(w)
  ss = set(substrings('weep'))
  print '%d substrings' % len(ss)
  good = ss & w
  print '%d good ones' % len(good)
  sgood = sorted(good, key=lambda w:(len(w), w))
  for aword in sgood:
    print aword

main()

будет излучать:

38617 words
31 substrings
5 good ones
we
ewe
pew
wee
weep

Конечно, как указывали другие ответы, организация ваших данных целенаправленно может значительно ускорить вашу рабочую среду - хотя лучшая организация данных для быстрого поиска анаграмм может быть разной... но это во многом будет зависеть от природы вашего словаря разрешенных слов (несколько десятков тысяч, как здесь - или миллионов?). Следует учитывать хэш-карты и "подписи" (на основе сортировки букв в каждом слове), а также попытки & c.

Ответ 6

Как Tim J, Эрик Липперт в блогах, где первое, что нужно сделать приходите мне на ум. Я хотел добавить, что он написал следующее о способах улучшения производительности своей первой попытки.

• Талисман назальности для аналитика султана
• Santalic tailfans, часть вторая

Ответ 7

Я считаю, что код Ruby в ответах на этот вопрос также решит вашу проблему.

Ответ 8

Недавно я очень много играл в Wordfeud на своем телефоне, и мне было любопытно, могу ли я придумать какой-нибудь код, чтобы дать мне список возможных слов. Следующий код использует ваши доступные исходные буквы (* для подстановочных знаков) и массив с основным списком допустимых слов (TWL, SOWPODS и т.д.) И генерирует список совпадений. Он делает это, пытаясь построить каждое слово в главном списке из ваших исходных писем.

Я нашел эту тему после написания своего кода, и это определенно не так эффективно, как метод Джона Пири или алгоритм DAWG, но все еще довольно быстро.

public IList<string> Matches(string sourceLetters, string [] wordList)
{
    sourceLetters = sourceLetters.ToUpper();

    IList<string> matches = new List<string>();

    foreach (string word in wordList)
    {
        if (WordCanBeBuiltFromSourceLetters(word, sourceLetters))
            matches.Add(word);
    }

    return matches;
}


public bool WordCanBeBuiltFromSourceLetters(string targetWord, string sourceLetters)
{
    string builtWord = "";

    foreach (char letter in targetWord)
    {
        int pos = sourceLetters.IndexOf(letter);
        if (pos >= 0)
        {
            builtWord += letter;
            sourceLetters = sourceLetters.Remove(pos, 1);
            continue;
        }


        // check for wildcard
        pos = sourceLetters.IndexOf("*");
        if (pos >= 0)
        {
            builtWord += letter;
            sourceLetters = sourceLetters.Remove(pos, 1);
        }


    }

    return string.Equals(builtWord, targetWord);

}