Алгоритм беспорядка слова

Question

Учитывая слово jumble (т.е. ofbaor), каков будет подход к расшифровке букв для создания реального слова (т.е. foobar)? Я мог видеть, что у этого есть пара подходов, и я думаю, что знаю, как я это сделаю в .NET, но мне любопытно посмотреть, как выглядят некоторые другие решения (всегда рад видеть, является ли мое решение оптимальным или нет).

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

редактировать: пожалуйста, опубликуйте псевдокод или реальный код, если можете; всегда приятно попробовать расширить знания языка, увидев такие примеры.

Answer 1

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

Таким образом, в качестве примера, слова «медведь» и «голый» должны быть в словаре следующим образом:

key    word
-----  ------
aber    bear
aber    bare

И если вам дано беспорядочное слово 'earb', вы бы отсортировали буквы по 'aber' и смогли найти оба возможных слова в словаре.

Answer 2

http://www.codeproject.com/KB/game/Anagrams2.aspx

Answer 3

В зависимости от длины строки, подход WhirlWind может быть быстрее, но альтернативный способ сделать это, который имеет более или менее сложность O (n), вместо создания всех перестановок строки и поиска их, просмотрите все слова в словаре и посмотрите, можно ли каждое из них построить из входной строки.

A действительно умный алгоритм, который заранее знает количество слов в словаре, может сделать что-то вроде этого:

sort letters in jumbled string
if factorial(length of jumbled string) > count of words in dictionary:
    for each word in dictionary:
       sort letters in dictionary word 
       if sorted letters in dictionary word == sorted letters in jumbled string:
           append original dictionary word to acceptable word list
else:
    create permutation list of jumbled letters
    for each permutation of letters:
        search in dictionary for permutation
        if permutation in dictionary:
            add word to acceptable word list

Answer 4

У CodeProject есть пара статей здесь и здесь . Второй использует рекурсию. Википедия также описывает пару алгоритмов здесь . В статье Википедии также упоминается программа под названием Jumbo, в которой используется более эвристический подход, который решает проблему, как это делает человек. Кажется, есть несколько подходов к проблеме.

Answer 5

Создайте все перестановки строки и найдите их в словаре.

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