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

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

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

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

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

Команда «getAnagrams» также является операцией O(n), которая ищет каждое слово в словаре, чтобы увидеть, является ли оно подмножеством поиска. Выполнение getAnagrams("радиотелеграфически")" (слово из 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']

Структура данных, которую вы хотите, называется направленным ациклическим графом слов (dawg) и описывается Эндрю Аппель и Гай Якобсен в своей статье «Самая быстрая в мире программа Scrabble», которую, к сожалению, они решили не размещать в свободном доступе в Интернете. Членство в ACM или университетская библиотека сделают это за вас.

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

Простой подход состоит в том, чтобы сгенерировать все «подстроки» и для каждой из них проверить, является ли она элементом множества допустимых слов. Например, в 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

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

Вам нужна реализация набора полномочий.

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

РЕДАКТИРОВАТЬ:

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

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>>

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

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));

Например, Тим Дж, блог Эрика Липперта, где в первую очередь нужно прийти мне на ум. Я хотел добавить, что он написал продолжение о том, как улучшить производительность своей первой попытки.

• Назальность талисман для султанши Аналитика
• Санталические хвостовые вентиляторы, часть вторая

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

В последнее время я много играл в 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);

}