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

1. Как предложенный Jason, подготовьте словарь, делающий хеш-таблицу с ключом, являющимся словом, отсортированным в алфавитном порядке, и оцените само слово (у Вас может быть несколько значений на ключ).
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)

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

, Конечно, я не протестировал это, и это - метод решения "в лоб".

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

Только что я записал сообщение в блоге о том, как быстро найти две анаграммы слова. Это работает действительно быстро: нахождение всех 44 анаграмм с двумя словами для слова с текстовым файлом больше чем 300 000 слов (4 мегабайта) занимает только 0,6 секунды в программе Ruby.

Два Word Anagram Finder Algorithm (в Ruby)

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

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

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

• Вычисляют код Вашего входного слова, как обрисовано в общих чертах выше.

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

Hope, которая была услужлива.

Книга , Программируя Жемчуг Jon Bentley касается этого вида материала вполне приятно. Обязательное для чтения.

Одна из оригинальных работ над программируемыми анаграммами была Michael Morton (г-н Machine Tool), с помощью инструмента по имени Magna Ars. Вот легкая статья на основе его работы.

Как я вижу его:

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

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

тогда от Вашего стартового слова, Вы находите набор букв:

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

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

редактирование: хм, это в значительной степени, что отправил Jason Cohen.

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

Посмотрите этот присвоение от отдела CSE Вашингтонского университета.

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

Предварительно обработайте:

Сборка trie с каждым листом как известное слово, ввел алфавитный порядок.

Во время поиска:

Рассматривают входную строку как мультимножество. Найдите первое подслово путем пересечения индекса trie как в поиске в глубину. При каждом ответвлении можно ли спросить, буква X в остатке от моего входа? Если у Вас есть хорошее представление мультимножества, это должно быть постоянным запросом времени (в основном).

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

Приращение эта процедура с memoization для более быстрых поисков на общих мультимножествах остатка.

Это довольно быстро - каждый trie обход, как гарантируют, даст фактическое подслово, и каждый обход занимает время в длине подслова (и подслова являются обычно симпатичной маленькой штопкой путем кодирования стандартов). Однако, если Вы действительно хотите что-то еще быстрее, Вы могли бы включать все n-граммы в Ваш предварительно обрабатывать, где n-грамма является любой строкой n слов подряд. Конечно, если W = #words, то Вы спрыгнете с индексного размера O (W) к O (W^n). Возможно, n = 2 реалистично, в зависимости от размера Вашего словаря.

Для каждого слова в словаре отсортируйте буквы в алфавитном порядке. Таким образом, "foobar" становится "abfoor".

Тогда, когда входная анаграмма войдет, отсортируйте ее буквы также, затем ищите ее. Это с такой скоростью, как поиск хеш-таблицы!

Для нескольких слов, Вы могли сделать комбинации отсортированных букв, сортируя, когда Вы идете. Все еще очень быстрее, чем генерация всех комбинаций.

(см. комментарии для большего количества оптимизации и деталей)

Большинство из этих ответов ужасно неэффективны и / или дадут решения, состоящие только из одного слова (без пробелов). Мое решение обрабатывает любое количество слов и очень эффективно.

Вам нужна структура данных в виде дерева. Вот полная реализация Python. Вам просто нужен список слов, сохраненный в файле с именем words.txt Вы можете попробовать список слов словаря Scrabble здесь:

http://www.isc.ro/lists/twl06.zip

MIN_WORD_SIZE = 4 # min size of a word in the output

class Node(object):
    def __init__(self, letter='', final=False, depth=0):
        self.letter = letter
        self.final = final
        self.depth = depth
        self.children = {}
    def add(self, letters):
        node = self
        for index, letter in enumerate(letters):
            if letter not in node.children:
                node.children[letter] = Node(letter, index==len(letters)-1, index+1)
            node = node.children[letter]
    def anagram(self, letters):
        tiles = {}
        for letter in letters:
            tiles[letter] = tiles.get(letter, 0) + 1
        min_length = len(letters)
        return self._anagram(tiles, [], self, min_length)
    def _anagram(self, tiles, path, root, min_length):
        if self.final and self.depth >= MIN_WORD_SIZE:
            word = ''.join(path)
            length = len(word.replace(' ', ''))
            if length >= min_length:
                yield word
            path.append(' ')
            for word in root._anagram(tiles, path, root, min_length):
                yield word
            path.pop()
        for letter, node in self.children.iteritems():
            count = tiles.get(letter, 0)
            if count == 0:
                continue
            tiles[letter] = count - 1
            path.append(letter)
            for word in node._anagram(tiles, path, root, min_length):
                yield word
            path.pop()
            tiles[letter] = count

def load_dictionary(path):
    result = Node()
    for line in open(path, 'r'):
        word = line.strip().lower()
        result.add(word)
    return result

def main():
    print 'Loading word list.'
    words = load_dictionary('words.txt')
    while True:
        letters = raw_input('Enter letters: ')
        letters = letters.lower()
        letters = letters.replace(' ', '')
        if not letters:
            break
        count = 0
        for word in words.anagram(letters):
            print word
            count += 1
        print '%d results.' % count

if __name__ == '__main__':
    main()

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

Он фильтрует короткие слова из вывода, иначе количество результатов будет огромным. Вы можете изменить настройку MIN_WORD_SIZE . Имейте в виду, что простое использование «астрономов» в качестве входных данных дает 233 549 результатов, если MIN_WORD_SIZE равно 1. Возможно, вы найдете более короткий список слов, который содержит только более распространенные английские слова.

Кроме того, сокращение «I» «m» (из одного из ваших примеров) не будет отображаться в результатах, если вы не добавите «im» в словарь и не установите MIN_WORD_SIZE на 2.

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

Кроме того, сокращение «Я» (из одного из ваших примеров) не будет отображаться в результатах, если вы не добавите «im» к словарь и установите MIN_WORD_SIZE равным 2.

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

Кроме того, сокращение «Я» (из одного из ваших примеров) не будет отображаться в результатах, если вы не добавите «im» к словарь и установите MIN_WORD_SIZE равным 2.

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

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

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