Мне нравится ваша идея отфильтровать список слов только до тех слов, которые можно составить из вводимых букв, и мне нравится идея попытаться связать их вместе, но я думаю, что есть несколько важных оптимизаций, которые вы могли бы реализовать. это, вероятно, немного ускорит процесс.
Для начала, вместо того, чтобы выбирать слово, а затем повторно сканировать весь словарь в поисках того, что осталось, я бы подумал о том, чтобы просто выполнить один проход фильтрации в начале, чтобы найти все возможные слова, которые можно составить из букв, которые у вас есть. Ваш словарь, вероятно, будет довольно колоссальным (я подозреваю, что 150 000+), поэтому повторное сканирование его после каждой точки принятия решения будет совершенно невозможным. Когда у вас есть набор слов, которые вы можете легально использовать в анаграмме, у вас остается проблема определения того, какие их комбинации можно использовать для формирования полной анаграммы предложения.
Я бы начал с поиска неупорядоченных списков слов, которые анаграммируют к цели, а не со всех возможных упорядоченных списков слов, потому что их нужно найти намного меньше. Когда у вас есть неупорядоченные списки, вы можете довольно быстро генерировать из них перестановки.
Чтобы сделать это, я бы использовал рекурсию с возвратом, где в каждой точке вы поддерживаете гистограмму оставшихся подсчетов букв. Вы можете использовать это, чтобы отфильтровать слова, которые больше не могут быть добавлены, и это существенно экономит ваши затраты на проверку всего словаря каждый раз. Я полагаю, что эта рекурсия во многом приведет к тупику, и что вы, вероятно, найдете все свои ответы без особых усилий.
По пути вы можете рассмотреть некоторые другие эвристики. Например, вы можете сначала начать с больших слов, чтобы вытащить как можно больше букв и сохранить низкий коэффициент ветвления. Для этого вы можете отсортировать список слов от самого длинного к самому короткому и попробовать слова в таком порядке. В качестве альтернативы вы можете попробовать сначала использовать наиболее ограниченные буквы, чтобы уменьшить коэффициент ветвления. Подобные эвристики, вероятно, будут очень хорошо работать на практике.
В целом вы по-прежнему смотрите на экспоненциальную работу в худшем случае, но это не должно быть слишком плохо для более коротких строк.
person
templatetypedef
schedule
22.11.2016
