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

Question

Например, если входная строка - helloworld, я хочу, чтобы вывод был таким:

do
he
we
low
hell
hold
roll
well
word
hello
lower
world
...

вплоть до самого длинного слова - анаграммы подстроки helloworld. Как в Эрудит например. Входная строка может быть любой длины, но редко больше 16 символов.

Я провел поиск и нашел такие структуры, как три, но я все еще не уверен, как на самом деле это сделать.

Answer 1

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

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

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

Answer 2

Я не мог устоять перед своей собственной реализацией. Он создает словарь, сортируя все буквы по алфавиту и сопоставляя их со словами, которые можно из них создать. Это операция запуска 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']

Answer 3

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

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

Answer 4

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

Answer 5

То, что вы хотите, это реализация блока питания .

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

EDIT:

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

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

Answer 6

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

}

Answer 7

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

Answer 8

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

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