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

Я не мог устоять перед своей собственной реализацией. Он создает словарь, сортируя все буквы по алфавиту и сопоставляя их со словами, которые могут быть созданы из них. Это операция запуска 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) , и он описан Эндрю Аппелем и Гаем Якобсеном в их статье «Самый быстрый в мире скрэббл» Программа », которую, к сожалению, они решили не предоставлять бесплатно в Интернете. Членство в 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));

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

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

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

• Ничего не сокращайте! BW_RCB01_SW что-то значил для команды, которая много лет назад занималась нашим CSS, но сейчас это ничего не значит для меня, и мне приходится работать в обратном направлении, чтобы попытаться перевести то, что BW_RCB01_SW соответствует для моих целей, и либо запомните этот перевод, либо запишите его где-нибудь. Лучше? черно-белый-boxtype1-bottomleft . Он длиннее, но также не требует розеттского камня.

• Используйте строчные буквы и символы подчеркивания или дефисы. Я предпочитаю дефисы, но это ' s полностью предпочтение. Не должно быть препятствий для использования дефисов, поскольку они не зарезервированы в CSS или HTML, а идентификаторы обрабатываются как буквальные строки на всех других языках. Строчные буквы - это весь опыт - слишком много часов потрачено на размышления, какого черта этот стиль не применим. pageContainerLeft не то же самое, что pageContainerleft .

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